Let $n$ be a positive integer and $a_1,a_2,\dots,a_n$ be integers. Function $f: \mathbb{Z} \rightarrow \mathbb{R}$ is such that for all integers $k$ and $l$, $l \neq 0$, $$\sum_{i=1}^n f(k+a_il)=0.$$Prove that $f \equiv 0$.
Problem
Source: Ukraine TST for IMO 2018 P12
Tags: algebra, function, combinatorics
Mindstormer
08.03.2019 02:34
Let $m=2\max(|a_i|)$. Note that $f(n)$ is uniquely determined by $f(n-m),\dots,f(n-1)$, so the whole $f$ is a recurrence of degree not more that $m$, so all $f(a)$ can be written as a linear combination of $f(1),\dots,f(m)$. Assume that $f$ is not $0$ everywhere, then there exists $1\leq j\leq m$ such that $f(j)\neq 0$, wlog $f(j)=1$.
Suppose that some of $f(1),\dots,f(m)$ are irrational, call them $\alpha_1,\dots,\alpha_k$. Then we have some equations of the kind $c_1\alpha_1+\dots+c_k\alpha_k=r$, where $c_i$ are integers and $r$ is rational. Obviously, no $k$ of these equations are linearly independent (otherwise some linear combination of them implies that $\alpha_1$ is rational), so any of them can be written as a linear combination of some $k-1$ (or less) of them. The set of solution to this system is some line with rational equation, so it has a rational point. Then $\alpha_i$ can be replaced with rational numbers.
Multiplying by a common denominator, we can make $f(1),\dots,f(m)$ integers. Pick a prime $q$ relatively prime to $n$. Since there are finitely many $m$-tuples modulo $q$, $f$ is periodic modulo $q$ with period $t$. Then $nf(k)\equiv f(k+a_1t)+\dots+f(k+a_nt)\equiv 0 \pmod q$, so $q|f(k)$ for all $k$. Function $f_1=f/q$ is also integer-valued and satisfies conditions, so we can indefinitely divide $f$ by $q$, contradiction.
dgrozev
09.03.2019 22:12
Let $T=\{a_1,a_2,\dots,a_n\}$. To illustrate the idea, suppose $f$ does not vanish at any point. Color $\mathbb{Z}$ in two colors: in black - the points where $f$ is positive, and in white - the rest of them, where $f$ is negative. According to the Gallai's theorem, there exist $k,\ell\in\mathbb{Z}$ such that the set $T' := k+\ell T=\{k+\ell x : x\in T\}$ is monochromatic. Moreover, there exists such set $T'\subset [1..N]$ for large enough $N$ It means all values of $f$ over $T'$ are either positive or negative, WLOG say positive. But then, $\displaystyle \sum_{i=1}^n f(k+a_i\ell)>0$, a contradiction. In general, $f$ may vanish in some points. To carry out the same idea, we first add appropriate functions to $f$, which satisfies the same functional equation, and get a function $g$ which satisfies the same condition as $f$, but does not vanish in a large enough interval. Applying the above trick, we get a contradiction. So, suppose there exists $a\in\mathbb{Z}$, such that $f(a)\neq 0$. Denote by $(*)$ the functional condition in the problem's statement. Notice that if $f$ satisfies $(*)$ then $C\cdot f(x-c)$ also does it, where $C$ and $c$ are some integer constants. Let $ x_1\geq 1$ be the first positive integer where $f$ vanishes. Let $f_1(x):= f(x)+C\cdot f(x-x_1+a)$. Since $f(x)\neq 0, x=1,2,\dots,x_1-1$, we may choose $C\in\mathbb{Z}, C>0$ large enough, such that $f_1(x)\neq 0, x=1,2,\dots,x_1-1$. But moreover, it also holds $f_1(x_1)\neq 0$, since $f(a)\neq 0$ and $f(x_1)=0$. Thus, we've constructed a function $f_1$ , which does not vanish in a segment larger than that of $f$. In such way, we may construct a function $f_m$ which does not vanish in the interval $[1..N]$, for as large $N$ as we want. As said above, we apply the Gallai's theorem and get a contradiction. Remark: The Gallai's theorem in one dimensional case says that given a finite set $T$ of lattice(integer) points and $\mathbb{Z}$ colored in $k$ colors, we can find a set $T'=k+\ell T$ of monochromatic points. In other words we can dilate and then translate $T$ and hit only monochromatic points. Moreover we may require $T'\subset [1..N]$ for large enough $N$, depending only on $T$ and $k$.
Pathological
10.03.2019 07:47
Let $k$ be an arbitrary integer. Let $b_0, b_1, b_2, \cdots, b_{n-1}$ denote $0, a_2 - a_1, a_3 - a_1, \cdots a_n - a_1,$ respectively. Then the condition can be rewritten as $f(k) + f(k+b_1l) + \cdots + f(k+b_{n-1}l) = 0,$ $\forall k, l \in \mathbb{Z}.$ Observe that $f(k+b_ib_n) + f(k+b_ib_n + b_1b_i) + f(k+b_ib_n + b_2b_i) + \cdots + f(k+b_ib_n + b_nb_i)$ for all $i$. Summing from $i = 1$ to $n$, we obtain that: $$\sum_{i = 1}^{n-1} \sum_{j = 0}^{n-1} f(x + b_i(b_n + b_j)) = 0.$$ However, it is obvious that: $$\sum_{j = 0}^{n-1} \sum_{i = 0}^{n-1} f(x + b_i(b_n + b_j)) = 0,$$ by using the condition on $k = x, l = b_n + b_j$ for each $j$, and so hence subtracting the two gives that: $$\sum_{j = 0}^{n-1} f(x + b_0(b_n+ b_j)) = 0,$$i.e. $nf(x) = 0 \Leftrightarrow f(x) = 0,$ as desired. $\square$
Tintarn
16.03.2019 19:28
Mindstormer wrote: Multiplying by a common denominator, we can make $f(1),\dots,f(m)$ integers. Pick a prime $q$ relatively prime to $n$. Since there are finitely many $m$-tuples modulo $q$, $f$ is periodic modulo $q$ with period $t$. Note that you only get $f(1),\dots,f(m) \in \mathbb{Z}$ and not $f(x) \in \mathbb{Z}$ for all $x$ (the linear recursion defining $f$ could have non-integer coefficients if some of the $a_i$ coincide). So the argument is not valid. However, it should be possible to modify it as follows: Clearly, the coefficients of the linear recursion are rational. Now, choose $q$ coprime to $n$ and additionally coprime to the denominators of these coefficients. Then we can argue as before.
Tintarn
16.03.2019 21:38
The solution in #4 is also invalid (and I am not sure how to fix it). Note that you cannot necessarily use the condition with $\ell=b_i$ or $\ell=b_n+b_j$ since these values might very well be zero and $\ell=0$ is not allowed.
Pathological
16.03.2019 23:53
Here is a fix to the issue that Tintarn mentioned: WLOG, let $a_1 \leq \cdots \leq a_n.$ Let $0 = b_1 < b_2 < \cdots < b_t$ be the distinct values among the $\{a_i - a_1\}$, and suppose that these values appear with multiplicity $c_1, c_2, \cdots, c_t.$ If $t = 1,$ then the problem is trivial. Otherwise, suppose that $t > 1.$ Then, the condition can be rewritten as $c_1f(k+b_1l) + c_2f(k+b_2l) + \cdots + c_tf(k+b_tl) = 0,$ $\forall k, l \in \mathbb{Z}, l \neq 0.$ Observe that $c_1c_if(k+b_ib_t+b_1b_i) + c_2c_if(k+b_ib_t + b_2b_i) + c_3c_if(k+b_ib_t + b_3b_i) + \cdots + c_tc_if(k+b_ib_t + b_tb_i) = 0$ for all $i>1$. Summing from $i = 2$ to $t$, we obtain that: $$\sum_{i = 2}^{t} \sum_{j =1}^{t} c_jc_if(x + b_i(b_t+b_j)) = 0.$$ However, it is obvious that: $$\sum_{j = 1}^{t} \sum_{i = 1}^{t} c_ic_jf(x + b_i(b_t + b_j)) = 0,$$ by using the condition on $k = x, l = b_t + b_j$ for each $j$, and so hence subtracting the two gives that: $$\sum_{j = 1}^{t} c_1c_jf(x + b_1(b_t+b_j)) = 0,$$i.e. $c_1(c_1 + c_2 + \cdots + c_t)f(x) = 0 \Leftrightarrow f(x) = 0,$ as desired. $\square$
mr.clock
05.09.2020 21:38
Van der Waerden's theorem.
Suppose $f$ is not identically zero.
Let $d= |a_{n}-a_{1}|$. First we make the following observation:
Claim. There are no $d$ consecutive zeros of $f$.
Proof. Look at the point where the sequence of zeros terminates. If we set $l=1$ and $k$ to a proper constant we can get all of $k+l a_{i}$ inside of the interval except for the last one which we can set to the first non-zero point. These $n$ numbers contradict the condition. $\square$
Therefore, there has to be a non-zero point in each of the intervals $[kd,(k+1)d )$. Suppose number $r_{i}+di$ is non-zero, where $r_{i}$ is the remainder modulo $d$. Now, suppose we colour the natural numbers in $d$ colours by the following rule: Colour $i$ with colour $j, j<d$ if $di+j$ is non-zero.
Now by Van der Waerden's, there is an arbitrarily long monochromatic arithmetic progression, which obviously corresponds to an arbitrarily long arithmetic progression of non-zero numbers. Now, we split the non-zero numbers into two colours based on their sign. Since we have an arbitrarily long arithmetic progression of non-zeros, by Van der Waerden we can find within it an arbitrarily long progression of the same sign. But this is obviously a contradiction since we can always find numbers of the form $k+la_{i}$ within a sufficiently long arithmetic progression.