Kvant Math Problem 574
Let
Verified: yes
Verdicts: PASS + PASS
Solve time: 13m05s
Source on kvant.digital
Problem
The finite sequence $a_1$, $a_2$, $\ldots$, $a_n$ consisting of the numbers 0 and 1 must satisfy the following condition: for every integer $k$ from 0 to $n-1$, the sum $$a_1a_{k+1}+a_2a_{k+2}+\ldots+a_{n-k}a_n$$ is an odd number.
- Construct such a sequence for $n=25$.
- Prove that such a sequence exists for some $n\gt1000$.
S. V. Konyagin
All-Union Mathematical Olympiad for School Students (1979, Grade 9)
Exploration
Let
$$S_k=a_1a_{k+1}+a_2a_{k+2}+\cdots+a_{n-k}a_n \qquad (0\le k\le n-1).$$
Only the parity of these sums matters. Writing everything modulo $2$ suggests introducing the polynomial
$$A(x)=a_1+a_2x+\cdots+a_nx^{n-1}$$
over the field $\mathbf F_2$.
The coefficient of $x^k$ in $A(x)A(x^{-1})$ is exactly
$$\sum_{i=1}^{n-k}a_i a_{i+k}=S_k$$
for $k\ge0$, and the coefficient of $x^{-k}$ is the same sum. Hence the condition becomes
$$A(x)A(x^{-1}) = \sum_{k=-(n-1)}^{n-1}x^k .$$
Multiplying by $x^{n-1}$ and introducing the reciprocal polynomial
$$A^*(x)=x^{n-1}A(x^{-1}),$$
we obtain
$$A(x)A^*(x)=1+x+\cdots+x^{2n-2}.$$
Thus the problem is equivalent to factoring the polynomial
$$R_m(x)=1+x+\cdots+x^{m-1}$$
with $m=2n-1$ into a polynomial and its reciprocal.
For $m=7$,
$$R_7(x)=1+x+\cdots+x^6 =(1+x+x^3)(1+x^2+x^3),$$
and the two factors are reciprocal. Hence $A(x)=1+x+x^3$ gives a solution for $n=4$.
The identity
$$R_{ab}(x)=R_a(x),R_b(x^a)$$
suggests building larger examples from the case $a=7$. Since
$$49=7^2,$$
we get
$$R_{49}(x)=R_7(x),R_7(x^7).$$
Replacing each factor $R_7$ by the product of the reciprocal pair above yields a solution for $m=49$, hence for $n=25$.
The delicate point is proving rigorously that the polynomial condition is exactly equivalent to the parity condition on all sums $S_k$.
Problem Understanding
We seek a finite binary sequence such that every autocorrelation sum
$$S_k=\sum_{i=1}^{n-k}a_ia_{i+k}$$
is odd.
This is a Type D problem. We must construct an example for $n=25$ and prove the existence of at least one example with $n>1000$.
The core difficulty is encoding the parity conditions simultaneously. Over $\mathbf F_2$, the oddness requirement becomes the statement that every $S_k$ is equal to $1$. A generating function converts these conditions into a single polynomial identity.
The answer will come from the factorization
$$1+x+\cdots+x^6=(1+x+x^3)(1+x^2+x^3),$$
together with the multiplicative identity
$$R_{ab}(x)=R_a(x)R_b(x^a).$$
Proof Architecture
Lemma 1. For a binary sequence with polynomial $A(x)=a_1+a_2x+\cdots+a_nx^{n-1}$, the condition that every $S_k$ is odd is equivalent to
$$A(x)A^*(x)=1+x+\cdots+x^{2n-2},$$
where $A^*(x)=x^{n-1}A(x^{-1})$; this follows by comparing coefficients modulo $2$.
Lemma 2. Over $\mathbf F_2$,
$$1+x+\cdots+x^6=(1+x+x^3)(1+x^2+x^3),$$
and the second factor is the reciprocal of the first; direct multiplication proves this.
Lemma 3. For every positive integers $a,b$,
$$R_{ab}(x)=R_a(x)R_b(x^a),$$
where $R_m(x)=1+x+\cdots+x^{m-1}$; expanding the product yields each power from $0$ to $ab-1$ exactly once.
Lemma 4. If
$$R_m(x)=B(x)B^*(x),$$
then
$$R_{7m}(x)=\bigl(B(x)(1+x^{m}+x^{3m})\bigr) \bigl(B(x)(1+x^{m}+x^{3m})\bigr)^*;$$
this follows from Lemmas 2 and 3.
The hardest step is Lemma 1, because every parity condition must be translated correctly into a coefficient identity.
Solution
Work over the field $\mathbf F_2$.
For a binary sequence $a_1,\dots,a_n$, define
$$A(x)=a_1+a_2x+\cdots+a_nx^{n-1},$$
and let
$$A^*(x)=x^{n-1}A(x^{-1}) =a_n+a_{n-1}x+\cdots+a_1x^{n-1}.$$
Consider
$$A(x)A(x^{-1}).$$
For $k\ge0$, the coefficient of $x^k$ in this Laurent polynomial is
$$\sum_{i=1}^{n-k}a_i a_{i+k}=S_k.$$
The coefficient of $x^{-k}$ is the same quantity. Hence the hypothesis that every $S_k$ is odd is equivalent, modulo $2$, to
$$A(x)A(x^{-1}) = \sum_{k=-(n-1)}^{n-1}x^k .$$
Multiplying by $x^{n-1}$ gives
$$A(x)A^*(x) = 1+x+\cdots+x^{2n-2}. \tag{1}$$
Thus a sequence exists exactly when the polynomial on the right side of (1) can be written as a polynomial times its reciprocal.
Now compute
$$(1+x+x^3)(1+x^2+x^3) = 1+x+x^2+x^3+x^4+x^5+x^6. \tag{2}$$
The polynomial $1+x^2+x^3$ is the reciprocal of $1+x+x^3$. Therefore
$$R_7(x):=1+x+\cdots+x^6 = B(x)B^*(x), \qquad B(x)=1+x+x^3. \tag{3}$$
Next,
$$R_{ab}(x) = (1+x+\cdots+x^{a-1}) (1+x^a+x^{2a}+\cdots+x^{(b-1)a}) = R_a(x)R_b(x^a). \tag{4}$$
Taking $a=b=7$ in (4),
$$R_{49}(x)=R_7(x)R_7(x^7).$$
Using (3),
$$R_{49}(x) = B(x)B^(x),B(x^7)B^(x^7).$$
Hence
$$R_{49}(x) = C(x)C^*(x),$$
where
$$C(x)=B(x)B(x^7) =(1+x+x^3)(1+x^7+x^{21}).$$
The degree of $C$ is $24$. Therefore, by (1), the coefficients of $C$ form a required sequence of length $25$.
Expanding $C$ modulo $2$,
$$C(x) = 1+x+x^3+x^7+x^8+x^{10}+x^{21}+x^{22}+x^{24}.$$
Thus one suitable sequence for $n=25$ is
$$(1,1,0,1,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,1,1,0,1).$$
For the second part, define
$$C_t(x)=\prod_{j=0}^{t-1}(1+x^{7^j}+x^{3\cdot7^j}).$$
Repeatedly applying (4) and (3) yields
$$R_{7^t}(x)=C_t(x)C_t^*(x).$$
The degree of $C_t$ is
$$\sum_{j=0}^{t-1}3\cdot7^j = 3\frac{7^t-1}{6} = \frac{7^t-1}{2}.$$
Therefore the coefficients of $C_t$ give a valid sequence of length
$$n=\frac{7^t+1}{2}.$$
Taking $t=4$,
$$n=\frac{7^4+1}{2} =\frac{2401+1}{2} =1201>1000.$$
Hence a required sequence exists for some $n>1000$.
The constructions are
$$\boxed{ (1,1,0,1,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0,0,1,1,0,1) }$$
for $n=25$, and
$$\boxed{ n=1201 }$$
for the second part.
Verification of Key Steps
The first delicate step is the passage from the parity conditions to equation (1). The coefficient of $x^k$ in $A(x)A(x^{-1})$ is
$$\sum_{i-j=k}a_i a_j.$$
Writing $j=i-k$ and restricting to indices between $1$ and $n$ gives
$$\sum_{i=k+1}^{n}a_i a_{i-k} = \sum_{r=1}^{n-k}a_r a_{r+k} = S_k.$$
Thus the coefficient really is the parity of the required sum.
The second delicate step is factorization (2). Multiplying directly,
$$\begin{aligned} (1+x+x^3)(1+x^2+x^3) &=1+x+x^2+x^3+x^2+x^3+x^4+x^5 \ &\qquad +x^3+x^4+x^5+x^6. \end{aligned}$$
Over $\mathbf F_2$, the coefficients of $x^2,x^3,x^4,x^5$ occur twice and cancel, leaving every power from $0$ through $6$ exactly once.
The third delicate step is the degree computation. Since
$$\deg(1+x^{7^j}+x^{3\cdot7^j})=3\cdot7^j,$$
the degree of the product is the sum of these degrees:
$$3(1+7+\cdots+7^{t-1}) = 3\frac{7^t-1}{6} = \frac{7^t-1}{2}.$$
Consequently the resulting sequence length is indeed
$$\frac{7^t-1}{2}+1=\frac{7^t+1}{2}.$$
Alternative Approaches
Instead of working with reciprocal polynomials, one may regard the sequence as the characteristic function of a subset of integers and interpret the conditions modulo $2$ as statements about difference representations. The factorization of $R_7(x)$ then becomes the statement that every residue modulo $7$ is represented an odd number of times as a difference of elements of a certain set. Iterating this construction in base $7$ produces the same family of examples.
The polynomial method is preferable because the autocorrelation conditions become a single identity, and the recursive construction follows immediately from the elementary factorization
$$1+x+\cdots+x^6=(1+x+x^3)(1+x^2+x^3).$$