Konstantin’s Weblog

Article on Mathematics, Chess, and Beauty

December 6, 2009 by zieglerk

Christian Hesse wrote in Mitteilungen der DMV 17 (2009) on Mathematik und Schach und Schönheit. The article is available as pdf.

Posted in math | Leave a Comment »

the group of units in a finite field is cyclic

December 6, 2009 by zieglerk

The goal is to give a quick proof of the well-known theorem quoted in the title.

We will use two facts:

Fact 1: The order of a group element divides the order of the group.

Fact 2: If $g$ is of order $m$ , then $g^i$ is of order $m/gcd(i,m)$ .

Fact 3: In any field, the equation $x^m=1$ has at most $m$ solutions $x$ .

Let $G$ be a commutative group with $n$ elements. For every divisor $m$ of $n$ we define $A_m$ as the set of all elements in $G$ of order $m$ .

Remark: If $x \in A_m$ , then $x^m = 1$ .

By Fact 1, the $A_m$ form a partition of $G$ :

$\displaystyle G = \bigcup_{m \mid n} A_m$ .

Example: Let $G = \mathbb{Z} / n\mathbb{Z}$ . For every $m \mid n$ the solutions of $x \cdot m = 0$ are given by $x = i \cdot \overline{n/m}, \quad 0 \leq i < m$ . Furthermore $A_m = \{i \cdot \overline{n/m} \colon 0 \leq i < m \text{ and } gcd(i,m)=1\}$ .

Lemma: Let $G$ be a commutative group with $n$ elements, where for every divisor $m$ of $n$ the equation $x^m = 1$ has at most $m$ solutions.

If $A_m$ is non-empty, then $\# A_m = \varphi (m)$ .
$A_m$ is never empty.

Proof:

Let $g \in A_m$ . Then $\# \langle g \rangle = m$ and the $m$ elements of $\langle g \rangle$ are all the solutions to $x^m = 1$ .
So, if $x$ solves $x^m = 1$, then $x \in \langle g \rangle$. By the remark above, this shows $A_m \subseteq \langle g \rangle = \{ g^i \}$ .
Furthermore $g^i$ is of order $m$ if and only if $gcd(i,m)=1$. Therefore
$\displaystyle \# A_m = \varphi(m)$ .
For $G = \mathbb{Z}/ n\mathbb{Z}$ we have $n/m \in A_m$ and therefore no $A_m$ is empty. For general $G$ satisfying the assumptions of the Lemma we have
$\displaystyle \sum_{m \mid n} \varphi(m) =$
$\displaystyle = \sum_{m \mid n} \# A_m \left( \mathbb{Z} / n \mathbb{Z} \right) =$
$\displaystyle = \# \mathbb{Z}/ n\mathbb{Z} = n = \# G = \sum_{m \mid n} \# A_m \leq \sum_{m \mid n} \varphi(m)$ .
And equality only if all $A_m$ are nonempty. But since equality is forced by the first and last term being equal this holds.

Corollary: Units in a finite field form a cyclic group

Proof: Units in a finite field satisfy the assumptions of the Lemma by Fact 3. Any element of the nonempty set $A_{n}$ is a generator.

Posted in math | Leave a Comment »

Article on Tropical Geometry

December 5, 2009 by zieglerk

The Computeralgebra-Rundbrief 44 (2009) featured Thomas Markwig, Tropische Geometrie. An english version of the article with an extended list of references is available as pdf.

Posted in math | Leave a Comment »

Article on Complex Multiplication

December 5, 2009 by zieglerk

The Computeralgebra-Rundbrief 45 (2009) featured Andreas Enge, Komplexe Multiplikation: von numerisch bis symbolisch. The article is available as pdf.

Posted in math | Leave a Comment »

Subtraction and Multiplication Problems by Tanya Khovanova

September 27, 2009 by zieglerk

I really like the problems Tanya Khovanova presents on her blog. It would be interesting to know how high school kids perform on the Subtraction and Multiplication Problems now compared to 50 years ago.

I particularly like the first one:

A stick has two ends. If you cut off one end, how many ends will the stick have left?

Posted in math | Leave a Comment »

article on base rate fallacy

July 28, 2009 by zieglerk

Bruce Schneier pointed in his blog to the following article on the base rate fallacy: A scanner to detect terrorists by Michael Blastland. It includes a nicely worked example and an even better graphic.

Posted in res publica | Leave a Comment »

Recognize your Primes

July 12, 2009 by zieglerk

After reading Tanya Khovanova’s Remember your Primes, I decided to do so. The description is due to John Conway.

Instead of memorizing all primes below 1000, it is easier to recognize composites:

1. Multiples of 2, 3, 5, 11 are easily detected.

2. Squares are known.

3. All that remains is to memorize 70 “non-trivial” composites (opposed to 168 primes in that range):

91, 119, 133, 161, 203, 217, 221, 247, 259, 287, 299, 301, 323, 329, 343, 371, 377, 391, 403, 413, 427, 437, 469, 481, 493, 497, 511, 527, 533, 551, 553, 559, 581, 589, 611, 623, 629, 637, 667, 679, 689, 697, 703, 707, 713, 721, 731, 749, 763, 767, 779, 791, 793, 799, 817, 833, 851, 871, 889, 893, 899, 901, 917, 923, 931, 943, 949, 959, 973, 989.

1. Remark:

If you are lazy, you can learn primes only up to 100. [...] [Y]ou need to remember only one number: 91.

2. Remark:

If you are very ambitious and plan to learn the primes up to 50,000, then the trick of learning non-trivial composites instead of primes is of no use to you. [...] The turning point is around 11,625: the number of primes below 11,625 equals the number of non-trivial composites below it.

3. As soon as you feel comfortable in the range below 1000 two more classes of composites become trivial to detect: Multiples of 7 and 13, since you can find the residue of a given number modulo 1001 by taking the alternating sum of three-digits.

Posted in math | Leave a Comment »

Verschlüsseln macht verdächtig

February 27, 2009 by zieglerk

Udo Vetter’s law blog cites under the title Verschlüsseln macht verdächtig from an interrogation transcript. [German]

Posted in res publica | Leave a Comment »

The “Broken Windows” Theory of Crimefighting

February 27, 2009 by zieglerk

Bruce Schneier’s blog post The “Broken Windows” Theory of Crimefighting quotes the article Breakthrough on ‘broken windows’ from The Boston Globe. Interesting information on what is effective — and what not.

Posted in res publica | Leave a Comment »

Question 4 from IMO 2008

February 24, 2009 by zieglerk

Problem: Find all functions $f: \mathbb{R}^{+} \to \mathbb{R}^{+}$ , s.t.

$\displaystyle \frac{f(w)^2 + f(x)^2}{f(y^2)+f(z^2)} = \frac{w^2+x^2}{y^2+z^2} \ \ \ \ \ (1)$

whenever $wx=yz$ . (Author: Hojoo Lee, South Korea)

Remark: Obvious solutions are $\mathop{id}: x \mapsto x$ and $\mathop{inv}: x \mapsto 1/x$ . We show, that those are also the only solutions.

Fact 1: $f(1) = 1$ .

Proof: Let $w=x=y=z=1$ .

Fact 2: $f(x^2) = f(x)^2$ .

Proof: Let $w=y=1$ and $x=z$ .

Using Fact 2, we can rewrite $(1)$ as

$\displaystyle \frac{f(w)+f(x)}{w+x}=\frac{f(y)+f(z)}{y+z} \ \ \ \ \ (2)$

whenever $wx=yz$ .

Fact 3: For every $x \in \mathbb{R}^{+}$

$\displaystyle f(x) = x \text{ or } f(x) = 1/x$ .

Proof: Let $w=x, y=1 \text{ and } z = x^2$ . Then $(2)$ implies

$\displaystyle \frac{2f(x)}{2x} = \frac{1+f(x)^2}{1+x^2}$

which is a quadratic equation for $f(x)$ with the two solutions $x$ and $1/x$ .

Fact 4 (

Non-mixing Lemma): If $f(x) = x$ for some $x \neq 1$ , then for all $x \in \mathbb{R}^{+}$ .

Proof: Assume $f(x) = x$ , for some $x \neq 1$ , but $f(w) \neq w$ for some $w \neq 1$ . By Fact 3, we know that in this case $f(w) = 1/w$ . We will show, that now the two possibilities for $f(xw)$ , i.e. $f(xw) = xw$ and $f(xw) = 1/(xw)$ both lead to contradictions.