# Bounds for the size of arrays with distinct subarray sums

Consider an array $$A$$ of length $$n$$ with $$A_i \in \{1,\dots,s\}$$ for some $$s\geq 1$$. For example take $$s = 6$$, $$n = 5$$ and $$A = (2, 5, 6, 3, 1)$$. Let us define $$g(A)$$ as the collection of sums of all the non-empty contiguously indexed subarrays of A. In this case $$g(A) = [2,5,6,3,1,7,11,9,4,13,14,10,16,15,17]$$

In this case all the sums are distinct. However, if we looked at $$g((1,2,3,4))$$ then the value $$3$$ occurs twice as a sum and so the sums are not all distinct.

For $$s \geq 1$$, I would like to understand what the largest $$n$$ is such that that there exists an array $$A$$ of length $$n$$ with all distinct $$g(A)$$. This question arose orginally as a coding competition and the answers for $$s = 1,\dots, 21$$ are $$n = 1, 2, 3, 3, 4, 5, 6, 6, 7, 8, 8, 9, 10, 11, 11, 11, 12, 13, 13, 14, 14$$.

On the assumption that an exact formula is hard to come by, is it possible to show its asymptotics? For example, is it true that $$n$$ is $$\Theta(s)$$?

Let $$0=:x_0 be the sums of initial segments of $$A$$. Then your condition is that the mutual differences of $$x$$'s are pairwise distinct, in other words, $$X=\{x_0,x_1,\dots,x_n\}$$ is a Sidon set. Additional requirement is that consecutive elements of $$X$$ differ at most by $$s$$. This of course means that $$n\leqslant s$$ and I claim that $$n=(1/3+o(1))s$$ is possible.

For this we may use one of standard constructions of Sidon set. Let $$p>2$$ be a prime number and consider the set of numbers $$x_k=2pk+\{k^2\}_p$$, where $$\{x\}_p$$ denotes a remainder of $$x$$ modulo $$p$$ and $$k$$ varies from 0 to $$p-1$$. Obviously $$x_{k+1}-x_k<3p$$ for all $$k=0,1,\dots,p-1$$ and the equation $$x_i+x_j=x_u+x_v$$ implies $$i+j=u+v$$, $$\{i^2\}_p+\{j^2\}_p=\{u^2\}_p+\{v^2\}_p$$ (considering remainders and quotients of both parts modulo $$2p$$), thus modulo $$p$$ we have $$i+j=u+v$$, $$i^2+j^2=u^2+v^2$$, $$(i-u)(i+u)=(v-j)(v+j)$$, $$(i-u)(i+u-v-j)=0$$, either $$i=u,v=j$$ or $$i+u=v+j=v+u+v-i$$, $$i=v,u=j$$. Therefore this is indeed a Sidon sequence and for any $$s\geqslant 3p-1$$ we get an array of length $$p-1$$. Since the primes number are frequent enough, this yields that $$n=(1/3+o(1))s$$ is possible.

The upper bound $$n\leqslant s$$ also may be improved using the idea of Erdos and Turan on Sidon sets. Namely, we may consider the differences $$x_j-x_i$$ for $$0 ($$t$$ is large but $$t=o(n)$$). There are $$tn+o(tn)$$ such differences, and their sum does not exceed $$\frac{t(t+1)}2x_n\leqslant \frac{t(t+1)}2 (s+(s-1)+\dots+(s-n))$$. Thus we get $$\frac12t^2n(s-n/2)\geqslant \frac{(tn)^2}2 (1+o(1))$$, $$n\leqslant \frac23s+o(s)$$.

Your sequence suggests that this upper bound is less or more tight.

• Thank you for this very clean answer. Do you know if there are tighter bounds known? – Anush Nov 13 '18 at 7:13
• I added an upper bound which looks tight, but I do not know how to improve the lower bound. There are more economic Sidon sets: you may take the field $\mathbb{F}_{p^2}$, then the elements of the form $g+i$, $i=0,1,\dots, p-1$, $g$ a fixed element not in $\mathbb{F}_p$, form a Sidon set in the multiplicative group of $\mathbb{F}_{p^2}$, this gives a Sidon set of size $p$ in $\{0,1,\dots,p^2-2\}$ (by the way $p$ may be a prime power, not necessary prime.) But are the differences between consecutive elements roughly speaking the numbers from $p/2$ to $3p/2$? – Fedor Petrov Nov 13 '18 at 8:15