F.L. Bauer’s Conjecture is F.L. Bauer’s Theorem

F.L.Bauer's Conjecture is F.L.Bauer's Theorem

During the recent Marktoberdorf Summer School - to be precise: during the dinner at the end of the Excursion on Wednesday 6 August 1986 - Fritz Bauer conveyed to me the following conjecture:

3: For positive integer $k$ and prime $p$ exceeding

Replacing $k$ by $k + 1$ ,we have to establish for natural

$$ \binom {(k + 1) \cdot p} {p} / (k + 1) - 1 i s a m u l t i p l e o f p ^ {3}, $$

or, by virtue of the definition of the binomial coef.

$$ \frac {(\underline {{P}} _ {i} : 1 \leq i < p : (k \cdot p + i))}{(\underline {{P}} _ {i} : 1 \leq i < p : i)} - 1 \quad \mathrm {i s a m u l t i p l e o f} p ^ {3}, $$

or, equivalently,

$$ (\underline {{P}} i: 1 \leq i < p: (k \cdot p + i)) - (p - 1)! \quad \mathrm {i s a m u l t i p l e o f} p ^ {3}. $$

To this end, we develop the product into powers of $k.p$ :

$$ \begin{array}{l} (P _ {i}: 1 \leq i < p: (k \cdot p + i)) \ = (p - 1)! + \ \end{array} $$

$$ \begin{array}{l} k \cdot p \cdot (\sum i: 1 \leq i < p: (p - 1)! / i) + \ (k \cdot p) ^ {2} \cdot (\sum i, j: 1 \leq i < j < p: (p - 1)! / (i \cdot j)) + \ h i g h e r p o w e r s o f k. p \ \end{array} $$

The demonstrandum thus follows from the following two lemmata:

Lemma 0: For prime $p$ such that $p > 3$

$$ (\sum i: 1 \leq i < p: (p - 1)! / i) \mod p ^ {2} = 0 $$

Lemma 1: For prime $p$ such that $p > 3$

$$ (\sum i, j: 1 \leq i < j < p: (p - 1)! / (i, j)) \mod p = 0 $$

In these summahions we are going to combine terms whose denominators sum up to (a multiple of) p . In the following, n is given by

$$ 2 \cdot n + 1 = p $$

For Lemma 0, this allows us to rewrite

$$ \begin{array}{l} (\leq i: 1 \leq i < p: (p - 1)! / i) \ = {\mathrm {s p l i t i n g t h e r a n g e} } \ (\underline {{S}} i: 1 \leq i \leq n: (p - 1)! / i) + (\underline {{S}} i: n < i < p: (p - 1)! / i) \ = {\mathrm {r e n a m i n g t h e s e c o n d d u m m y :} i := p - j } \ (\underline {{S}} i: 1 \leq i \leq n: (p - 1)! / i) + (\underline {{S}} j: 1 \leq j \leq n: (p - 1)! / (p - j)) \ = {\mathrm {c o m b i n g s u m m a t i o n s o v e r e q u a l r a n g e s} } \ (\sum i: 1 \leq i \leq n: (p - 1)! / i + (p - 1)! / (p - i)) \ = {\mathrm {a r i t h m e t i c} } \ p \cdot (\underline {{\leq}} i: 1 \leq i \leq n: (p - 1)! / (i \cdot (p - i))) \ \end{array} $$

and, consequently, the proof obligation of Lemma 0 can be discharged by showing Lemma 2:

Lemma 2 For prime $p$ such that $p > 3$ (and $2 \cdot n + 1 = p$ ) $(\underline{S} i: 1 \leq i \leq n: (p - 1)! / (i \cdot (p - i))) \mod p = 0$ or, equivalently, $(\underline{S} i_j: 1 \leq i < j < p \land i + j = p: (p - 1)! / (i_j)) \mod p = 0$ .

From the last rewriting we see that Lemma 2 is concerned with a subset of the terms summed in Lemma 1 . Before pursuing Lemma 2 , let us inspect the remaining terms in Lemma 1 . Since $i + j = p \lor i + j < p \lor i + j > p$

we analyse

$$ \begin{array}{l} (\leq i, j: 1 \leq i < j < p \land i + j < p: (p - 1)! / (i, j)) \ = {\mathrm {a r i t h m e t i c} } \ (\leq i, j: 1 \leq i < j < p - i: (p - 1)! / (i, j)) \ = {\mathrm {n e s t i n g s u m m a t i o n s} } \ (\underline {{S}} i: 1 \leq i \leq n: (\underline {{S}} j: i < j < p - i: (p - 1)! / (i \cdot j))) \ \end{array} $$

in which the inner summation can be rewritten

$$ \begin{array}{l} (\sum j: i < j \leq n: (p - 1)! / (i \cdot j)) + (\sum j: n < j < p - i: (p - 1)! / (i \cdot j)) \ = {\mathrm {r e n a m i n g t h e s e c o n d d u m m y}: j := p - h } \ (\underline {{S}} j: i < j \leq n: (p - 1)! / (i \cdot j)) + (\underline {{S}} h: i < h \leq n: (p - 1)! / (i \cdot (p - h))) \ = {\mathrm {c o m b i n i n g s u m m a t i o n s o v e r e q u a l r a n g e s} } \ (S _ {j}: i < j \leqslant n: (p - 1)! / (i \cdot j) + (p - 1)! / (i \cdot (p - j))) \ = {\mathrm {a r i t h m e t i c} } \ p \cdot (\underline {{S}} _ {j}: i < j \leq n: (p - 1)! / (i \cdot j \cdot (p - j))) \ \end{array} $$

We trust that, after the above, the reader believes

as well that the terms with $i + j > p$ add up to a multiple of $p$ . Hence also the proof obligation of Lemma 1 has been reduced to proving Lemma 2.

On the proof of Lemma 2 I spent at least five vain hours looking for a nice combinatorial argument in the style of my proof of Wilson's Theorem (EWD742). [This was psychologically very strange because all the time I knew that the effort was ill-directed since ruling out the primes 2 and 3 would not fit in it. And yet I tried for more than five hours ....]

Eventually I found an argument by considering

(i) that Lemma 2 is the same as

computing (S:1≤i<n: 1/(i.(p-i)) by finding the common denominator leads to a fraction with a numerator that is a multiple of $p$ "

(ii) the computation under (i) can be done while reducing all intermediate results modulo $p$ . So much for the heuristics.

For given $p$ we consider the $p$ "rest classes", i.e. the infinite sets of integers such that any two of them differ by a multiple of $p$ . For any rational fraction $x / y$ such that $y \mod p \neq 0$ we define the rest class $[x / y]$ by

$$ [ x / y ] = {z | x \mod p = y \cdot z \mod p } $$

(On account of $y$ mod $p \neq 0$ and $p$ being prime

$$ y: (x \mod p = y \cdot z \mod p) $$

has solutions that form a rest class.)

We can now define an arithmetic on rest classes

$$ \begin{array}{l} b y [ a ] + [ b ] = [ a + b ] [ a ] - [ b ] = [ a - b ] \ [ a ] \cdot [ b ] = [ a \cdot b ] \ [ a ] / [ b ] = [ a / b ] \quad \mathrm {p r o v i d e d} [ b ] \neq [ 0 ], \ \end{array} $$

$$ \begin{array}{l} a ] = [ b ] \equiv [ a ] - [ b ] = [ 0 ] \ [ x / y ] = [ (x + p) / y ] \ [ x / y ] = [ x / (y + p) ] \ [ x ] \cdot [ y ] = [ 0 ] \equiv [ x ] = [ 0 ] \vee [ y ] = [ 0 ] e t c. \ \end{array} $$

The important thing to observe is that among the p rest classes there are n+1 "squares", i.e. rest classes of the form $\left\lbrack {x}^{2}\right\rbrack$ . They are [0],with [0] as its only square root and the n "positive squares" $\left\lbrack {i}^{2}\right\rbrack$ for $1 \leq i \leq n$ with [i] and [p-i] as their square roots. From

$$ \begin{array}{l} [ i ^ {2} ] = [ j ^ {2} ] \ = [ i ^ {2} - j ^ {2} ] = [ 0 ] \ = [ i - j ] = [ 0 ] \vee [ i + j ] = [ 0 ] \ \end{array} $$

we conclude that [0] and the n positive squares are all different.

After these preliminaries we are ready to attack Lemma 2

$$ \begin{array}{l} [ (\underline {{S}} _ {i}: 1 \leq i \leq n: (p - 1)! / (i. (p - i))) ] \ = [ (p - 1)! ] \cdot (\underline {{\underline {{S}}}} _ {i}: 1 \leq i \leq n: [ 1 / (i \cdot (p - i)) ]) \ = - [ (p - 1)! ] \cdot (\underline {{S}} _ {i}: i \leqslant i \leqslant n: [ 1 / i ^ {2} ]) \ = - [ (p - 1)! ] \cdot (\sum i: 1 \leq i \leq n: [ i ^ {2} ]) \ = - [ (p - 1)! ] \cdot [ (\underline {{S}} _ {i}: i \leq i \leq n: i ^ {2}) ] \ = - [ (p - 1)! ] \cdot [ n \cdot (n + 1) \cdot (2 \cdot n + 1) / 6 ] \ = [ 0 ] \ \end{array} $$

$$ \begin{array}{l} *) 1 \leq i \leq j \leq n \land [ 1 / i ^ {2} ] = [ 1 / j ^ {2} ] \ = 1 \leq i \leq j \leq n \land [ (i ^ {2} - j ^ {2}) / i ^ {2} \cdot j ^ {2} ] = [ 0 ] \ \Rightarrow i = j, h e n c e i f i s a s u m o f n d i f f e r e n t s q u a r e s. \ \end{array} $$

As $\left\lbrack 0\right\rbrack$ is not among them,it is the sum of the n positive squares.

$$ \begin{array}{l} \ast \ast) \mathrm {R e m e n b e r} 2 \cdot n + 1 = p; n \cdot (n + 1) \cdot p / 6 \ h a s a f a c t o r p f o r p r i m e p \geq 5 \ \end{array} $$

Austin 22 August 1986

prof. d. Edsger W. Dgiksha

Department of Computer Sciences

The University of Texas at Austin

Austin TX 78712- 1188

USA