Math Challenge - June 2021

[fresh_42]

Problem #8:

By definition

\begin{align*}
H (p) = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{p -1} = \frac{a}{b} .
\end{align*}

If we can show that:

\begin{align*}
(p - 1)! \left( 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{p - 1} \right) = k p^2
\end{align*}

where $k$ is an integer then we would have

\begin{align*}
H (p) = \frac{k p^2}{(p - 1)!} .
\end{align*}

Since none of the factors in $(p - 1)!$ divide $p$ no $p$ in the numerator can be canceled out. Thus $p^2$ would divide the numerator.

In the polynomial

\begin{align*}
g (x) = (x-1)(x-2) \cdots (x - (p - 1)) = x^{p-1} + a_1 x^{p - 2} + \cdots + a_{p -2} x + a_{p - 1} \quad (*)
\end{align*}

the term $a_{p - 2}$ is given by

\begin{align*}
a_{p -2} = - (p -1)! \left( 1 + \frac{1}{2} + \cdots + \frac{1}{p - 1} \right)
\end{align*}

If we can show that $- a_{p - 2} = k p^2$ that will solve the problem.

We have $a_{p - 1} = (p - 1)!$.

Fermat's little theorem says that $a^{p - 1} \equiv 1 \; (\text{mod } p)$ for any integer $a$. It follows that modulo $p$, that $x^{p - 1} - 1$ has the roots $p - 1$ roots $1,2, \dots , p-1$. So that:

\begin{align*}
h (x) = x^{p - 1} - 1 \equiv (x-1)(x-2) \cdots (x - (p - 1)) \; (\text{mod } p) .
\end{align*}

Note that modulo $p$, $h (x)$ and $g (x)$ have the same roots.

Also, Wilson's theorem says that:

\begin{align*}
(p - 1)! \equiv -1 \; (\text{mod } p)
\end{align*}

Using all of the above in the polynomial $g (x) - h (x)$ we obtain

\begin{align*}
f (x) & = g (x) - h (x)
\nonumber \\
& = x^{p-1} + a_1 x^{p - 2} + \cdots + a_{p -2} x + a_{p - 1} - x^{p - 1} + 1
\nonumber \\
& \equiv a_1 x^{p - 2} + a_2 x^{p -3} + \cdots + a_{p -2} x \; (\text{mod } p)
\nonumber \\
& \equiv 0 .
\end{align*}

As this is a polynomial of degree $p - 2$ with the $p - 1$ solutions by Lagrange's theorem $p$ divides all the coefficients.

Putting $x = p$ in $(*)$ gives

\begin{align*}
(p-1)! = p^{p-1} + a_1 p^{p - 2} + a_2 p^{p -3} + \cdots + a_{p -2} p + a_{p - 1}
\end{align*}

Subtracting $(p - 1)!$ from both sides, dividing by $p$, and then rearranging gives

\begin{align*}
- a_{p - 2} = p^{p-2} + a_1 p^{p - 3} + \cdots + a_{p - 3} p .
\end{align*}

As we are taking $p \geq 5$, and as each of the coefficients $a_1, a_2, \dots a_{p - 3}$ is proportional to $p$ the RHS is equal to $k p^2$ where $k$ is an integer.

If $p$ were equal to 3 we couldn't say that the term $a_1 p^{p - 3}$ is proportional to $3^2$ as $a_1 p^{p - 3} = a_1$. The result clearly doesn't apply to $H (3)$:

\begin{align*}
H (3) = 1 + \frac{1}{2} + \frac{1}{3} = \frac{11}{6} .
\end{align*}

Right. The result is known as the Theorem of Wolstenholme.

 

[fresh_42]

Problem #6:

By definition

\begin{align*}
d = \min_{(x,y) \in C^2 , x \not= y} d (x,y)
\end{align*}

where $d(x,y)$ be the Hamming distance of $x$ and $y$. A bound is proved by bounding the quantity

\begin{align*}
\sum_{(x,y) \in C^2 , x \not= y} d (x,y)
\end{align*}

in two different ways. On the one hand, there are $\# C$ choices for $x$ and for each such choice, there are $\# C - 1$ choices for $y$. Since by definition $d (x,y) \geq d$ for all $x$ and $y$ ($x \not= y$), it follows that

\begin{align*}
\sum_{(x,y) \in C^2 , x \not= y} d (x,y) \geq \# C (\# C - 1) d .
\end{align*}

The other inequality is obtained by writing down all the $\# C$ codewords of $C$ into a $\# C \times n$-matrix. Let $n_{i , \alpha}$ denote the number of times the element $\alpha$ of the alphabet (with $q$ elements) occurs in the $i$th column. For each choice of $\alpha$ in the $i$th column there are $\# C - n_{i , \alpha}$ elements not equal to $\alpha$ in the same column. Then

\begin{align*}
\sum_{(x,y) \in C^2 , x \not= y} d (x,y) & = \sum_{i = 1}^n \sum_{\alpha} n_{i , \alpha} (\# C - n_{i , \alpha})
\nonumber \\
& = \sum_{i = 1}^n \left( (\# C)^2 - \sum_\alpha n_{i , \alpha}^2 \right) \qquad ( \sum_{\alpha} n_{i , \alpha} = \# C)
\nonumber \\
& \leq \sum_{i = 1}^n \left( (\# C)^2 - \frac{(\# C)^2}{q} \right) \qquad ( (\# C)^2 = (\sum_{\alpha} n_{i , \alpha} \cdot 1)^2 \leq (\sum_{\alpha} n_{i , \alpha}^2) (\sum_{\alpha} 1^2) )
\nonumber \\
&= n \cdot (\# C)^2 \cdot \left( 1 - \frac{1}{q} \right) .
\end{align*}

Combining the two bounds gives

\begin{align*}
\# C (\# C - 1) d \leq (\# C)^2 \cdot n \cdot \left( \frac{q - 1}{q} \right)
\end{align*}

or

\begin{align*}
d (\# C - 1) \leq \# C \cdot n \cdot \left( \frac{q - 1}{q} \right) \qquad (*)
\end{align*}

If $d < n \cdot \dfrac{q - 1}{q}$ the bound $(*)$ can be rearranged as

\begin{align*}
\# C \leq \frac{d}{d - n \cdot \dfrac{q - 1}{q}} .
\end{align*}

The bound is called Plotkin bound.