2
$\begingroup$

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!)

$\endgroup$
1
  • $\begingroup$ Besides $n=2$, do you know any cases where this is doable? $\endgroup$ Jun 19, 2018 at 18:47

5 Answers 5

10
$\begingroup$

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$.

$\endgroup$
3
  • 1
    $\begingroup$ Will, very nice! $\endgroup$
    – Lucia
    Jun 19, 2018 at 20:32
  • $\begingroup$ 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. $\endgroup$ Jun 19, 2018 at 20:40
  • $\begingroup$ @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. $\endgroup$
    – Will Sawin
    Jun 20, 2018 at 5:09
8
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$ Jun 19, 2018 at 19:02
  • $\begingroup$ @GerhardPaseman Your point is much better than mine. So that takes out $n \equiv 3$ or $0 \bmod 4$. $\endgroup$ Jun 19, 2018 at 19:13
  • $\begingroup$ 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. $\endgroup$ Jun 19, 2018 at 19:18
  • $\begingroup$ 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). $\endgroup$ Jun 19, 2018 at 19:38
  • $\begingroup$ 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. $\endgroup$ Jun 19, 2018 at 19:42
3
$\begingroup$

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$.

$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$ Jun 21, 2018 at 16:49
  • $\begingroup$ 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. $\endgroup$ Jun 21, 2018 at 16:56
  • $\begingroup$ 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. $\endgroup$ Jun 21, 2018 at 17:12
  • $\begingroup$ Bijecting, not bisecting. Gerhard "Ran Out Of Edit Time" Paseman, 2018.06.21. $\endgroup$ Jun 21, 2018 at 17:19
  • $\begingroup$ @GerhardPaseman: the bottom line is, you agree - or should I further explain anything? $\endgroup$
    – Seva
    Jun 21, 2018 at 17:37
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jun 19, 2018 at 20:09
  • 1
    $\begingroup$ Thanks for checking. I am now getting that too. Gerhard "Back To The Starbucks Napkin" Paseman, 2018.06.19. $\endgroup$ Jun 19, 2018 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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