# A Nice Problem In Additive Number Theory

$$\color{red}{\mathbf{Problem\!:}}$$ $$n\geq3$$ is a given positive integer, and $$a_1 ,a_2, a_3, \ldots ,a_n$$ are all given integers that aren't multiples of $$n$$ and $$a_1 + \cdots + a_n$$ is also not a multiple of $$n$$. Prove there are at least $$n$$ different $$(e_1 ,e_2, \ldots ,e_n ) \in \{0,1\}^n$$ such that $$n$$ divides $$e_1 a_1 +\cdots +e_n a_n$$

$$\color{red}{\mathbf{My Approach\!:}}$$

We can solve this by induction (not on $$n$$, as one can see in the answer provided by Thomas Bloom given in the link below). But I approached it in a different way using trigonometric sums. Can we proceed in this way successfully?

$$\color{blue}{\text{Reducing modulo n we can assume that 1\leq a_j\leq n-1}.}$$

Throughout this partial approach, $$i$$ denotes the imaginary unit, i.e. $$\color{blue}{i^2=-1}$$.

Let $$z=e^{\frac{2\pi i}{n}}$$. Then $$\frac{1}{n}\sum_{k=0}^{n-1}z^{mk} =1$$ if $$n\mid m$$ and equals $$0$$ if $$n\nmid m$$.

Therefore, if $$N$$ denotes the number of combinations $$e_1a_1+e_2a_2+\cdots+e_na_n$$ with $$(e_1,e_2,\ldots, e_n)\in\{0,1\}^n$$ such that $$n\mid(e_1a_1+e_2a_2+\cdots+e_na_n)$$, then $$N$$ is equal to the following sum,

$$\sum_{(e_1,e_2,\ldots, e_n)\in\{0,1\}^n}\left(\frac{1}{n}\sum_{j=0}^{n-1}z^{j(e_1a_1+e_2a_2+\cdots+e_na_n)}\right)$$

By swapping the order of summation we get, $$N=\frac{1}{n}\sum_{j=0}^{n-1}\prod_{k=1}^{n}(1+z^{ja_k})$$

Clearly, the problem is equivalent to the following inequality:

$$\left|\sum_{j=0}^{n-1}\prod_{k=1}^{n}(1+z^{ja_k})\right|\geq n^2\tag{1}$$

Can we prove this inequality? Any hint or help will be appreciated. Thank you!

$$\color{red}{\mathrm{Update:}}$$ This is actually IMO shortlist $$1991$$ problem $$13$$. No proofs are available except using induction. So if we can prove inequality $$(1)$$, it will be a completely new proof! In fact, inequality $$(1)$$ is itself very interesting.

$$\color{red}{\mathrm{One\, more\, idea\, (maybe\, not\, useful):}}$$

Let $$\theta_{jk}=\frac{ja_k\pi}{n}$$ and $$A=\sum_{k=1}^{n}a_k$$, then we get, $$(1+z^{ja_k})=\left(1+\cos\left(\frac{2ja_k\pi}{n}\right)+i\sin\left(\frac{2ja_k\pi}{n}\right)\right)=2\cos(\theta_{jk})(\cos(\theta_{jk})+i\sin(\theta_{jk}))$$ Therefore,

$$\left|\sum_{j=0}^{n-1}\prod_{k=1}^{n}(1+z^{ja_k})\right|=2^n\left|\sum_{j=0}^{n-1}\prod_{k=1}^{n}\cos(\theta_{jk})e^{i\theta_{jk}}\right|$$

So we get one more equivalent inequality,

$$\left|\sum_{j=0}^{n-1}\prod_{k=1}^{n}\cos(\theta_{jk})e^{i\theta_{jk}}\right|=\left|\sum_{j=0}^{n-1}e^{i\frac{\pi Aj}{n}}\prod_{k=1}^{n}\cos(\theta_{jk})\right|\geq\frac{n^2}{2^n}\tag{2}$$

$$\color{red}{\text{Remark:}}$$ According to the hypothesis of the question, $$n\nmid A$$. Therefore $$e^{i\frac{\pi A}{n}}\neq\pm1$$.

Also posted on Mathoverflow

The only combinatorial solution using induction is available here.

• @Peter yeah, we can take $n\geq 3$.
– ShBh
Commented Jul 9, 2020 at 18:19
• (+1) Nr. 18, I wanted to use the pigeonhole-principle , but I could not establish a proof yet. Commented Jul 9, 2020 at 18:20
• Now posted to MO, mathoverflow.net/questions/365527/… with no notice to either site. Please don't do that. Commented Jul 13, 2020 at 12:06
• This result and the combinatorial proof given in Mathoverflow have to be refered to: -J.E. Olson, A Problem of Erdos on abelian groups, Combinatorica 7(3) (1987) 285-289 Commented Jul 14, 2020 at 22:52
• This is a solid approach (one that works well in many situations). The next key observation is that the summand corresponding to $j=0$ is very large (it equals $2^n$ in the notation of equation (1)). So it suffices to prove, say, that every other summand is less than $(2^n-n^2)/(n-1)$ in absolute value. Commented Jul 8, 2023 at 19:03