# find a set of integers where {$a_i + a_j | 1 \le i \le j \le n$} leave distinct remainders when divided by $n(n+1)/2$

For each integer $n>1$, find a set of $n$ integers {$a_1, a_2, ..., a_n$} such that the set of numbers {$a_i + a_j | 1 \le i \le j \le n$} leave distinct remainders when divided by $n(n+1)/2$. If such set of integers does not exist, give a proof.

I know ideally I should show what I've attempted thus far but I'm completely lost and don't really know how to get started. I guess WLOG I can let $a_1 < a_2 <...<a_n$ and I also know that I should have from $0 \mod (n(n+1)/2)$ to $n(n+1)/2 - 1 \mod (n(n+1)/2)$ for $a_i + a_j$ but otherwise I'm not sure.

(I did ask this on mathematics stack exchange and I really appreciate the members' help there but I'd like more help!)

• Besides $n=2$, do you know any cases where this is doable? – David E Speyer Jun 19 '18 at 18:47

This is impossible for $n>2$. This relies on an idea of Seva, now deleted.

Let $m = n (n+1)/2$ For any nontrivial character $\chi$, we have

$$\left( \sum_{ a\in A}\chi(a)\right) ^2 + \sum_{a \in A} \chi^2(a) = 2 \sum_{a \in \mathbb Z/m} \chi(a)=0$$

In particular, if $m$ is even, then taking $\chi$ a character of order $2$, we get a square plus something positive is zero, a contradiction (recovering a result of Gerhard Paseman).

Because of this $m$ is odd, so squaring acts as a permutation of the nontrivial characters. Because we can square some number of times and get back to itself, $x= \sum_{a \in A} \chi(a)$ satisfies $x^{2^k} = \pm x$ and thus is a root of unity or zero.

Hence $$nm= \sum_{\chi} \left| \sum_{a \in A} \chi(a) \right|^2 \leq n^2 + (m-1)$$ with the $n^2$ from the trivial character.

This gives $m (n-1) \leq n^2-1$, so $m \leq n+1$, which implies $n\leq 2$.

• Will, very nice! – Lucia Jun 19 '18 at 20:32
• Kudos! Can this be used to say something about (lack of) equidistribution mod d for sufficiently large divisors d of m? Gerhard "This Should Be In Literature" Paseman, 2018.06.19. – Gerhard Paseman Jun 19 '18 at 20:40
• @GerhardPaseman We don't use ever the relation of $n$ with $m$, or the fact that there are no repetitions, so this shows the sumset of $n$ numbers cannot be equidistributed mod $d$ unless $d \leq n+1$ and $d$ is odd. – Will Sawin Jun 20 '18 at 5:09

This is not possible for sufficiently large $n$. Put $N= n(n+1)/2$ and we may clearly assume that the set lies in $[1,N]$. Then this set of $n$ integers must have all sums of pairs $a+b$ being distinct (apart from the relation $a+b=b+a$). Such sets are called Sidon sets, and Erdos and Turan showed that a Sidon set in $[1,N]$ has at most $\sqrt{N} + O(N^{\frac 14})$ elements. Since $n \ge \sqrt{2N}-1$ clearly this is a contradiction for large $n$.

First observation: There are no solutions for $n \equiv 3 \bmod 8$ or $4$ or $8 \bmod 16$. Let $k$ be the number of $a_i$ which are odd, then the number of $a_i+a_j$ which are odd is $k(n-k)$.

If $n \equiv 3 \bmod 8$, then $k(n-k)$ is even, but the number of odd elements modulo $\tfrac{n(n+1)}{2}$ is odd.

If $n \equiv 4$ or $8 \bmod 16$, then $k(n-k)$ is either $0$ or $3 \bmod 4$, but the number of odd elements modulo $\tfrac{n(n+1)}{2}$ is $1$ or $2 \bmod 4$.

• Also, when n(n+1)/2 is even, the number of odd sums (O times E) should be equal to the number of even sums, leading to the (insoluble in mostly positive integers) equation $2OE = O^2 + E^2 + O + E$. Gerhard "Leading To More Congruence Incongruencies" Paseman, 2018.06.19. – Gerhard Paseman Jun 19 '18 at 19:02
• @GerhardPaseman Your point is much better than mine. So that takes out $n \equiv 3$ or $0 \bmod 4$. – David E Speyer Jun 19 '18 at 19:13
• One might be able to extend this so that, for at least one prime p dividing n(n+1)/2, there has to be an imbalance in sum totals mod p. This would make a nice theorem for you David. Gerhard "For Me A Hard Theorem" Paseman, 2018.06.19. – Gerhard Paseman Jun 19 '18 at 19:18
• The odd primes dividing $n$ don't help: If the $a_i$ are equidistributed modulo $p$, so are the $a_i+a_j$. Similarly, I get that, if $k$ of the $a_i$ are $0$, $1$, ..., $p-2$ modulo $p$ and $k-1$ are $p-1 \bmod p$, then the $a_i+a_j$ are equidistributed (again, for $p$ odd). – David E Speyer Jun 19 '18 at 19:38
• When n=2 and 3 divides 3, I agree it doesn't help. What if n=5? Are there any subsets of size 5 whose sums are mod 3 equidistributed? Gerhard "It's Looking Like Research Mathematics" Paseman, 2018.06.19. – Gerhard Paseman Jun 19 '18 at 19:42

This is just a slightly more explicit and self-contained version of Lucia's answer.

Let $N:=n(n+1)/2$. If all the sums $a_i+a_j$ with $1\le i<j\le n$ have distinct remainders upon division by $N$, the so do all the differences $a_i-a_j$ since $a_i-a_j\equiv a_s-a_t\pmod N$ implies $a_i+a_t\equiv a_j+a_s\pmod N$. However, there are $n(n-1)$ differences $a_i-a_j$ and just $N-1$ non-zero remainders. Thus, $$n(n-1) \le N-1 = \frac{(n-1)(n+2)}2,$$ and it follows that $2n\le n+2$; hence, $n\le 2$.

• This is a really clever sleight of mind argument. Can you expand on the word "Thus", as I am not seeing how what follows "Thus" is a consequence of what comes before? Gerhard "Otherwise It Is Quite Nice" Paseman, 2018.06.21. – Gerhard Paseman Jun 21 '18 at 16:49
• To be clear, I think this is a brilliant example, and I want it to stay. I am just not clear if it is an example of proof or of fallacy. Gerhard "We Need To Understand These" Paseman, 2018.06.21. – Gerhard Paseman Jun 21 '18 at 16:56
• Ah. For me, the missing step is "if ai - aj agrees with as-at mod N, then (since at is not as) either i=s and j=t or else two sums are also the same mod N, so the assumption implies there have to be n(n-1) distinct nonzero differences mod N." I vote proof now. (Originally, I thought you were bisecting differences to sums.) Gerhard "Thank You For Your Patience" Paseman, 2018.06.21. – Gerhard Paseman Jun 21 '18 at 17:12
• Bijecting, not bisecting. Gerhard "Ran Out Of Edit Time" Paseman, 2018.06.21. – Gerhard Paseman Jun 21 '18 at 17:19
• @GerhardPaseman: the bottom line is, you agree - or should I further explain anything? – Seva Jun 21 '18 at 17:37

This is not an answer, but a derivative question worth pursuing. I put it here in hopes someone can complete it to an answer which solves the posted question.

Let p be a prime dividing n+1. Divide a given set A of integers into residue classes mod p, so there are a_j many members of A equal to j mod p. When I feel up to it, I will write out the equations for how many of the sums of unordered pairs from A add up to a number which is k mod p. The upshot is that for a set A to satisfy the required conditions mod n(n+1)/2, it needs to satisfy an equidistribution system of equations mod p for each such p. In other words, if S_c is the count of such sums from A with sum equal to c mod p, then S_c=S_b for c different from b mod p. We have p choose 2 equations of a form like $$\sum_{j+k=c \bmod p, j \lt k} a_ja_k + \sum_{j+j=c \bmod p} (a_j^2 + a_j)/2= \sum_{j+k=b \bmod p, j \lt k} a_ja_k + \sum_{j+j=b \bmod p} (a_j^2 + a_j)/2$$.

The question now is are there any tuples of nonnegative integers $a_j$ whose sum is $n$ and which satisfy the above system? For n=2 and p=3, we have (0,1,1). Are there any others?

It is easy to verify (by running through 3-partitions of 5) that for n=5 and p=3, there are no (error: at least one, thanks David Speyer) 5- sets A which sums are equidistributed mod 3.

Edit

It turns out there are others. Let d be an odd divisor of n+1. One can look at the addition table of 0,..,n to see that there are an equal number of representatives mod d among all ordered pairs of sums. As d is odd, this reduces to equidistribution mod d among the unordered pairs of their sums. "Removing" the last column (addition by n) shows that the equidistribution remains when restricted to the set A=(0,1,...,n-1). So there is a solution to the system of equations above, not just for odd primes p, but also for odd divisors d of (n+1) (and for odd d dividing n). So the approach suggested above does not directly lead to a proof of the nonexistence of such sets mod m (because p=d is too small). It might yield something for large divisors d of m, however.

End Edit

Gerhard "Is This In The Literature?" Paseman, 2018.06.19.

• One of us is getting the $n=5$, $p=3$ computation wrong. The multiset $\{ 0,0,1,1,2 \}$ achieves each sum modulo $3$ in $5$ ways. – David E Speyer Jun 19 '18 at 20:09
• Thanks for checking. I am now getting that too. Gerhard "Back To The Starbucks Napkin" Paseman, 2018.06.19. – Gerhard Paseman Jun 19 '18 at 20:17