4
$\begingroup$

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)$?

$\endgroup$
7
$\begingroup$

Let $0=:x_0<x_1<x_2<\dots<x_n$ 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<j-i\leqslant t$ ($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.

$\endgroup$
  • $\begingroup$ Thank you for this very clean answer. Do you know if there are tighter bounds known? $\endgroup$ – Anush Nov 13 '18 at 7:13
  • 1
    $\begingroup$ 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$? $\endgroup$ – Fedor Petrov Nov 13 '18 at 8:15

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.