Problem A. 727. (May 2018)

A. 727. For any finite sequence $\displaystyle (x_1,\ldots,x_n)$, denote by $\displaystyle N(x_1,\ldots,x_n)$ the number of ordered index pairs $\displaystyle (i,j)$ for which $\displaystyle 1\le i<j\le n$ and $\displaystyle x_i=x_j$. Let $\displaystyle p$ be an odd prime, $\displaystyle 1\le n<p$, and let $\displaystyle a_1,a_2,\ldots,a_n$ and $\displaystyle b_1,b_2,\ldots,b_n$ be arbitrary residue classes modulo $\displaystyle p$. Prove that there exists a permutation $\displaystyle \pi$ of the indices $\displaystyle 1,2,\ldots,n$ for which

$\displaystyle N\big(a_1+b_{\pi(1)},a_2+b_{\pi(2)},\ldots,a_n+b_{\pi(n)}\big) \le \min \big(N(a_1,a_2,\ldots,a_n), N(b_1,b_2,\ldots,b_n) \big). $

(5 pont)

Deadline expired on June 11, 2018.

Solution (based on the solutions submitted by Attila Gáspár and Dávid Matolcsi). Throughout the solution, the prime $\displaystyle p$ will be fixed. $\displaystyle S_m$ denotes the set of permutations of the set $\displaystyle \{1,2,\ldots,m\}$. For any permutation $\displaystyle \sigma\in S_m$, $\displaystyle \sgn\sigma$ denotes the sign of $\displaystyle \sigma$; that is, $\displaystyle +1$ for even permutations and $\displaystyle -1$ for odd permutations.

Notice that the value of $\displaystyle N(\ldots)$ does not depend on the arguments and the role of the two sequences is symmetric.

First we prove the problem statement in the particular case when $\displaystyle a_1,\ldots,a_n$ are distinct.

Claim I: If $\displaystyle n<p$, the modulo $\displaystyle p$ residue classes $\displaystyle a_1,\ldots,a_n$ are distinct, and $\displaystyle b_1,\ldots,b_n$ are arbitrary modulo $\displaystyle p$ residue classes, then there exist a permutation $\displaystyle \pi\in S_n$ so that $\displaystyle a_1+b_{\pi(1)}, \ldots, a_n+b_{\pi(n)}$ are distinct.

We present two proofs for Claim I. Both proofs use the so-called Vandermonde-polynomials.

The Vandermonde-polynomial of the variables $\displaystyle x_1,\ldots,x_n$ is $$\begin{align*} V(x_1,x_2,\ldots,x_n) &= \prod_{1\le i\lt j\le n} (x_j-x_i) = \\ &= \det\begin{pmatrix} 1 & x_1 & x_1^2 & \ldots & x_1^{n-1} \\ 1 & x_2 & x_2^2 & \ldots & x_2^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & x_n & x_n^2 & \ldots & x_n^{n-1} \\ \end{pmatrix} = \\ &= \sum_{\sigma\in S_n} (\sgn\sigma)\cdot x_1^{\sigma(1)-1}x_2^{\sigma(2)-1}\cdots x_n^{\sigma(n)-1}. \end{align*}$$ Two basic properties of the Vandermonde-polynomials we will use are:

$\displaystyle \bullet$ The value of the Vandermonde-polynomial is nonzero if and only if the arguments are distinct.

$\displaystyle \bullet$ The Vandermonde-polynomial is an alternating polynomial; that is, for any permutation $\displaystyle \pi\in S_n$,

$\displaystyle V(x_{\pi(1)},\ldots,x_{\pi(n)}) = (\sgn\pi)\cdot V(x_1,\ldots,x_n). $

First proof for Claim I. Our main tool is the following

Lemma. Let $\displaystyle F$ be an algebraic field, and let $\displaystyle f(x_1,\ldots,x_n)$ be a polynomial over $\displaystyle F$.
Let $\displaystyle t_1,\ldots,t_n$ be nonnegative integers with $\displaystyle \deg f=t_1+\ldots+t_n$;
let $\displaystyle S_1,\ldots,S_n\subset F$ be sets with $\displaystyle |S_i|>t_i$ for every index $\displaystyle i$;
finally suppose that in the expansion of $\displaystyle f(x_1,\ldots,x_n)$, the coefficient of $\displaystyle x_1^{t_1}\ldots x_n^{t_n}$ is nonzero.
Then there exist elements $\displaystyle s_1\in S_1,\ldots.,s_n\in S_n$ such that $\displaystyle f(s_1,\ldots,s_n)\ne0$.

The Lemma and a possible proof can be found in Noga Alon's paper Combinatorial Nullstellensatz (Theorem 1.2.). The theorem is sometimes called as "combinatorial Nullstellensatz", although Theorem 1.1. would correspond to Hilbert's Nullstellensatz.

For proving Claim I, let $\displaystyle F$ be the $\displaystyle p$-element field (the field of the modulo $\displaystyle p$ residue classes),

$\displaystyle f(x_1,\ldots,x_n) = V(x_1,\ldots,x_n) \cdot V(x_1+b_1,\ldots,x_n+b_n), $

let $\displaystyle t_1=\ldots=n-1$ (then $\displaystyle \deg f=t_1+\ldots+t_n=n(n-1)$), and let $\displaystyle S_1=\ldots=S_n=\{a_1,\ldots,a_n\}$.

For determining the coefficient of $\displaystyle x_1^{n-1}\ldots x_n^{n-1}$, notice that $$\begin{align*} f(x_1,\ldots,x_n) &= \left( \sum_{\sigma\in S_n} (\sgn\sigma)\cdot \prod_{i=1}^n x_i^{\sigma(i)-1} \right) \left( \sum_{\tau\in S_n} (\sgn\tau)\cdot \prod_{i=1}^n (x_i+a_i)^{\tau(i)-1} \right) = \\ &= \sum_{\sigma\in S_n} \sum_{\tau\in S_n} (\sgn\sigma)\cdot (\sgn\tau)\cdot \left( \prod_{i=1}^n x_i^{\sigma(i)-1} \right) \left( \prod_{i=1}^n (x_i+a_i)^{\tau(i)-1} \right). \end{align*}$$ The monomial $\displaystyle x_1^{n-1}\ldots x_n^{n-1}$ occurs in those terms where $\displaystyle \sigma(i)+\tau(i)=n+1$. Let $\displaystyle \varphi\in S_n$ be the permutation with $\displaystyle \varphi(i)=n+1-i$; then $\displaystyle \tau=\varphi\circ\sigma$ and $\displaystyle (\sgn\sigma)(\sgn\tau) = \sgn(\sigma\tau^{-1}) =\sgn\varphi$. Hence, the coefficient of $\displaystyle x_1^{n-1}\ldots x_n^{n-1}$ if $\displaystyle f$ is $\displaystyle n!\cdot\sgn\varphi$, which is not the $\displaystyle 0$ element of $\displaystyle F$.

By the Lemma, there are some elements $\displaystyle s_1,\dots,s_n\in\{a_1,\ldots,a_n\}$ such that $\displaystyle f(s_1,\ldots,s_n)\ne0$. That means $\displaystyle V(s_1,\ldots,s_n)\ne0$ and $\displaystyle V(s_1+b_1,\ldots,s_n+b_n)\ne0$. The condition $\displaystyle V(s_1,\ldots,s_n)\ne0$ satisfied only if $\displaystyle s_1,\ldots,s_n$ are distinct, so $\displaystyle (s_1,\ldots,s_n)$ is some permutation of the sequence $\displaystyle (a_1,\ldots,a_n)$: $\displaystyle s_i=a_{\pi(i)}$. The second condition $\displaystyle V(s_1+b_1,\ldots,s_n+b_n=V(a_{\pi(1)}+b_1,\ldots,a_{\pi(n)}+b_n)\ne0$ yields that the residue classes $\displaystyle a_{\pi(1)}+b_1,\ldots,a_{\pi(n)}+b_n$ are distinct. That proves Claim I.

Second proof for Claim I (Dávid Matolcsi). We show that

$\displaystyle \sum_{\pi\in S_n} V(x_1+y_{\pi(1)},\ldots,x_n+y_{\pi(n)}) = n! \cdot V(x_1,\ldots,x_n). \tag{1} $

Let

$\displaystyle P(x_1,\ldots,x_n,y_1,\ldots,y_n) = \sum_{\pi\in S_n} V(x_1+y_{\pi(1)},\ldots,x_n+y_{\pi(n)}). $

Expand the polynomial $\displaystyle V(x_1+y_1,\ldots,x_n+y_n)$ by the variables $\displaystyle x_1,\ldots,x_n$:

$\displaystyle V(x_1+y_1,\ldots,x_n+y_n) = \sum_{k_1,\ldots,k_n\ge0} C_{k_1,\ldots,k_n}(y_1,\ldots,y_n) \, x_1^{k_1}\ldots x_n^{k_n}, $

where the exponents $\displaystyle k_1,\ldots,k_n$ are nonnegative integers, and for every such sequence of exponents, $\displaystyle C_{k_1,\ldots,k_n}(y_1,\ldots,y_n)$ is some polynomial.

Substitute into the definition of $\displaystyle P$, order the arguments of the Vandermonde-polynomial by the indices of $\displaystyle y_i$, and interchange the summations: $$\begin{align*} P(x_1,\ldots,x_n,y_1,\ldots,y_n) &= \sum_{\pi\in S_n} V(x_1+y_{\pi(1)},\ldots,x_n+y_{\pi(n)}) = \\ &= \sum_{\pi\in S_n} (\sgn\pi^{-1})\cdot V(x_{\pi^{-1}(1)}+y_1,\ldots,x_{\pi^{-1}(n)}+y_n) = \\ &= \sum_{\tau\in S_n} (\sgn\tau) \sum_{k_1,\ldots,k_n\ge0} C_{k_1,\ldots,k_n}(y_1,\ldots,y_n) \, x_{\tau(1)}^{k_1}\ldots x_{\tau(n)}^{k_n} = \\ &= \sum_{k_1,\ldots,k_n\ge0} C_{k_1,\ldots,k_n}(y_1,\ldots,y_n) \sum_{\tau\in S_n} (\sgn\tau)\cdot x_{\tau(1)}^{k_1}\ldots x_{\tau(m)}^{k_n} = \\ &= \sum_{k_1,\ldots,k_n\ge0} C_{k_1,\ldots,k_n}(y_1,\ldots,y_n) \cdot\det \begin{pmatrix} x_1^{k_1} & \ldots & x_1^{k_n} \\ \vdots & \ddots & \vdots \\ x_n^{k_1} & \ldots & x_n^{k_n} \\ \end{pmatrix}. \end{align*}$$ If any two of $\displaystyle k_1,\ldots,k_n$ are equal then the last determinant is zero. Otherwise, if $\displaystyle k_1,\ldots,k_n$ are distinct, then by $\displaystyle \deg P\le\tbinom{n}{2}=0+1+\ldots+(n-1)$, the exponents $\displaystyle (k_1,\dots,k_n)$ must be a permutation of $\displaystyle (0,1,\ldots,n-1)$, and the polynomial $\displaystyle C_{k_1,\ldots,k_n}(y_1,\ldots,y_n)$ must be a constant. Therefore, in the sum above, the variables $\displaystyle y_1,\ldots,y_n$ cancel out. Hence,

$\displaystyle P(x_1,\ldots,x_n,y_1,\ldots,y_n) = P(x_1,\ldots,x_n,0,\ldots,0) = $

$\displaystyle = \sum_{\pi\in S_n} V(x_1+0,\ldots,x_n+0) = n! \cdot V(x_1,\ldots,x_n); $

the identity (1) has been proved.

Substituting $\displaystyle a_1,\ldots,a_n$ and $\displaystyle b_1,\ldots,b_n$ in (1), $$\begin{align*} \sum_{\pi\in S_n} V(a_1+b_{\pi(1)},\ldots,a_n+b_{\pi(n)}) &\equiv n! \cdot V(a_1,\ldots,a_n) = \\ &= n! \cdot \prod_{i\lt j} (a_j-a_i) \not\equiv 0 \pmod{p}. \end{align*}$$ The R.H.S. is nonzero, so the sum on the L.H.S. has at least one nonzero term. So, there exist a permutation $\displaystyle \pi\in S_n$ with

$\displaystyle V(a_1+b_{\pi(1)},\ldots,a_n+b_{\pi(n)}) = \prod_{i\lt j} (a_j+b_{\pi(j)}-a_i-b_{\pi(i)})\ne0. $

But this indicates that the residue classes $\displaystyle a_1+b_{\pi(1)},\ldots,a_n+b_{\pi(n)}$ are distinct.

Claim II: If $\displaystyle 0\le n<p$, the there is a $\displaystyle \pi\in S_n$, such that $\displaystyle N(a_1+b_{\pi(1)}, a_2+b_{\pi(2)}, \ldots, a_n+b_{\pi(n)})\le N(a_1, a_2, \dots, a_n)$.

Proof (Attila Gáspár). We prove by induction on $\displaystyle n$. The Claim is trivial for $\displaystyle n=0$ and $\displaystyle n=1$. Let $\displaystyle 2\le n<p$, and assume that the Claim is true for smaller values.

Let $\displaystyle k$ be the number of different elements among $\displaystyle a_1, a_2, \dots, a_n$. Re-arrange the elements in such an order that $\displaystyle a_1,a_2,\ldots,a_k$ are distinct.

Notice that each of $\displaystyle a_{k+1},\ldots,a_n$ is listed exactly once among $\displaystyle a_1,a_2,\ldots,a_k$, so there are exactly $\displaystyle n-k$ pairs $\displaystyle i,j$ of indices with $\displaystyle i\le k<j$ and $\displaystyle a_i=a_j$. Therefore,

$\displaystyle N(a_1,\ldots,a_n) = (n-k) + N(a_{k+1},\ldots,a_n). \tag{2} $

By Claim I there is a permutation $\displaystyle \pi_1$ of $\displaystyle 1, 2, \dots, k$ such that $\displaystyle a_1+b_{\pi_1(1)}, a_2+b_{\pi_1(2)}, \ldots, a_k+b_{\pi_1(k)}$ are distinct. By the induction hypothesis, there is a permutation $\displaystyle \pi_2$ of $\displaystyle k+1, k+2, \dots, n$ such that

$\displaystyle N(a_{k+1}+b_{\pi_2(k+1)}, a_{k+2}+b_{\pi_2(k+2)}, \ldots, a_n+b_{\pi_2(n)})\le N(a_{k+1}, a_{k+2}, \dots, a_{n}). \tag{3} $

Merge $\displaystyle \pi_1$ and $\displaystyle \pi_2$ to a new permutation $\displaystyle \pi$.

By the definition of $\displaystyle \pi_1$, the classes $\displaystyle a_1+b_{\pi(1)},\ldots,a_k+b_{\pi(k)}$ are distinct. For each $\displaystyle j$ with $\displaystyle k<j\le n$, there is at most one index $\displaystyle i\le k$ with $\displaystyle a_i+b_{\pi(i)}=a_j+b_{\pi(j)}$. For this reason,

$\displaystyle N(a_1+b_{\pi(1)},\ldots,a_n+b_{\pi(n)}) \le (n-k) + N(a_{k+1}+b_{\pi(k+1)},\ldots,a_n+b_{\pi(n)}). \tag{4} $

The estimates (4,3,2) together provide

$\displaystyle N(a_1+b_{\pi(1)},\ldots,a_n+b_{\pi(n)}) \le N(a_1,\ldots,a_n), $

that finishes the proof of the Claim.

Solution of the problem: By the symmetry we can assume $\displaystyle N(a_1, \dots, a_n)\le N(b_1, \dots, b_n)$. Then the problem statement is the same as Claim II.

Statistics:

3 students sent a solution.

5 points: Gáspár Attila.

2 points: 1 student.

0 point: 1 student.

Problems in Mathematics of KöMaL, May 2018

3 students sent a solution.
5 points:	Gáspár Attila.
2 points:	1 student.
0 point:	1 student.

Already signed up?
New to KöMaL?