# What is the smallest $k$ such that two disjoint sets remain unequal when elements are considered modulo $k$?

Let $X$ be a finite set of positive integers. Define $X \bmod k$ as multiset of positive integers obtained by mod operation on every element of $X$. For example, {3, 5, 8} $\bmod$ 3 = {0, 2, 2}. Two multisets are equal iff they have the same elements with identical frequency.

Let $A$ and $B$ be two subsets of {1, 2, 3, ..., n - 1, n} such that $|A| = |B| = m$, $A \cap B = \emptyset$. What is the minimum $k$ (as a function of $n$ and $m$) such that the multisets $A \bmod k \neq B \bmod k$. Consider for example $A$ = {2, 4, 11, 15} and $B$ = {6, 8, 13, 17} for which $A \bmod i = B \bmod i$, for $i = 2, 3$ but $A \bmod 4 \neq B \bmod 4$.

I also posted the question at math.stackexchange. For $m$ = 1, $k = O(\log n)$.

-
I looked a bit at the case $m=2$ at mathoverflow.net/questions/98529/… –  Gerry Myerson Jun 1 '12 at 0:17

Improved Answer Since Gerry Meyerson has not spelled out his interesting insights let me take a stab with apologies ahead of time for what I am missing.

Let $A,B$ be disjoint $m$ element subsets of $\lbrace 0,1,\cdots,n\rbrace$ with $0 \in A$ and $A,B$ equivalent as multisets $\mod{i}$ for $2 \le i \le k$ but not for $i=k+1$. What can we say about the possible values of $m,n,k?$

• If $A$ and $B$ are an appropriate pair of disjoint sets, so are those sets shifted down by a common amount: $\lbrace x-j \mid x \in A\rbrace$ and $\lbrace y-j \mid y \in B\rbrace$ So we may assume that the minimum element of $A$ is $0$ . Shift everything up by $1$ in the end if you wish. I've also given $k+1$ the role previously played by $k.$

• Hence we will have $A=\lbrace a_1=0,a_2,\cdots,a_m\rbrace$ and $B=\lbrace b_1,b_2,\cdots,b_m\rbrace$ where the $b_j$ are such that for every $2 \le i \le k$ there is a $j$ with $b_j \equiv 0 \mod i.$ Note that this means the product $b_1b_2\cdots b_m$ is a multiple of $L=L(k),$ the lcm of the integers up to $k.$ Also, for $k$ not too small, one would expect $\sum a_j = \sum b_j$. Certainly $\sum a_j\equiv \sum b_j \mod{L(k)}$ because this congruence holds $\mod{i}$ for $2 \le i \le k.$ Given how large $L(k)$ is, equality seems a sure thing. later In fact it is not unusual to have $\sum a_j^t = \sum b_j^t$ for $0 \le t \le u$ for $u=m-1.$ This is partially explained below.

• in the case $m=2$ it is sufficient to have $A=\lbrace 0,b_1+b_2\rbrace$ and $B=\lbrace b_1,b_2\rbrace .$ where ,as above, $b_1,b_2$ are such that for every $2 \le i \le k$ either $b_1 \equiv 0 \mod i$ (in which case $b_2 \equiv b_1+b_2 \mod i$) or the similar situation with the roles reversed. This is also essentially necessary, Any solution will be $A=\lbrace 0,a_2\rbrace$ and $B=\lbrace b_1,b_2\rbrace$ with $b_1,b_2$ as above. But then $0+a_2 \equiv b_1+b_2 \mod i$ for $2 \le i \le k$ and the smallest positive solution of this is $a_2=b_1+b_2$ (assuming that $b_1,b_2$ are not maliciously chosen bigger than they need to be.)

• notice that $ab$ will be a multiple of $L(k).$ These pairs have been studied in this question where it turns out that for the "best" solutions, sometimes $ab=L(k)$ and other times $ab=2L(k).$

• When $ab=L$ then $b$ is the product of some or all the primes $\frac{n}{2} \lt p \le n$ and $a$ is the lcm of all the other prime powers $p^i \le n.$ When $ab=2L$ we have the similar description except that $b$ is twice the product of some of the primes $\frac{n}{3} \lt p \le n.$

Later Thoughts Let $A$ and $B$ be two sets of integers and consider the polynomial $f_{AB}(x)=\sum_{a \in A}x^a-\sum_{b \in B}x^b.$ Then the following conditions are equivalent:

• $A$ and $B$ are congruent as multisets for all $2 \le i \le k$
• $F_{AB}$ is divisible by $x^i-1$ for all $2 \le i \le k$
• $F_{AB}$ is divisible by the $i$th cyclotomic polynomial $\phi_i$ for all $2 \le i \le k$

If $S$ is a set of integers such that for every $2 \le i \le k$ there is an element of $S$ congruent to $0 \mod{i}$ then the polynomial $G_S=\Pi_{s\in S}x^s-1$ will serve as a suitable $F$ provided that it has all coefficients $0,1$ and $-1$. Perhaps this is part of what Gerry was suggesting. Notice that this construction gives $(x-1)$ as a factor $|S|$ times. We only need once, however it is certainly helpful for having few coefficients to have factors of this form.

As observed above, all solutions with $m=2$ are of this form. Below are what I think are some minimal solutions for $m=3,4.$ In some cases I have listed $F_{AB}$ in a factored form. The format is $A,B,k,F_{AB}.$ $P_d$ means a polynomial of degree $d$, typically with $P_d(1)=1$ See a note at the very end about the Prouhet-Tarry-Escott problem.

For $m=3$ if the maximal element is not in the same set as $0$:

$[0, 1, 2], [4, 5, 6], 4,G_{\lbrace3,4\rbrace}/(x-1)$

$[0, 7, 14], [2, 4, 15], 5,$

$[0, 14, 16], [4, 6, 20], 6, G_{\lbrace 4,6,10 \rbrace}$

$[0, 17, 19], [5, 7, 24], 7, G_{\lbrace 5,7,12 \rbrace}$

$[0, 13, 47], [5, 7, 48], 8, G_{\lbrace 5,6,7,8 \rbrace}P_{24}/(x^2-1)$

$[0, 34, 86], [14, 16, 90], 10$

$[0, 106, 158], [18, 70, 176], 11$

$[0, 92, 166], [22, 56, 180], 12,G_{\lbrace 10,14,22,36\rbrace}P_{98}\phi_8/(x^2-1)$

If the maximal element is in the same set as $0$:

$[0, 1, 6], [2, 3, 4], 2$

$[0, 2, 7], [4, 5, 6], 3$

$[0, 5, 10], [1, 6, 8], 4$

$[0, 1, 14], [4, 5, 6], 5$

$[0, 7, 21], [1, 12, 15], 6$

$[0, 2, 43], [7, 8, 30], 7$

$[0, 11, 58], [16, 18, 35], 8$

$[0, 11, 98], [18, 35, 56], 9$

$[0, 34, 127], [7, 64, 90], 10$

Here are the similar results for $m=4$

$[0, 1, 2, 3], [4, 5, 6, 7], 2$

$[0, 1, 2, 3], [6, 7, 8, 9], 4$

$[0, 7, 8, 9], [3, 4, 5, 12], 5,G_{\lbrace3,4,5\rbrace}$

$[0, 9, 10, 11], [4, 5, 6, 15], 6,G_{\lbrace 4,5,6\rbrace}$

$[0, 17, 19, 22], [7, 10, 12, 29], 7,G_{\lbrace7,10,12\rbrace}$

$[0, 12, 29, 31], [5, 7, 24, 36], 8,G_{\lbrace5,7,24\rbrace}$

$[0, 1, 2, 7], [3, 4, 5, 6], 2$

$[0, 1, 2, 9], [3, 4, 5, 6], 3$

$[0, 2, 7, 9], [1, 3, 6, 8], 4$

$[0, 2, 11, 13], [5, 6, 7, 8], 6$

$[0, 9, 17, 26], [2, 5, 21, 24], 7,G_{\lbrace 2,5,7,12\rbrace}$

$[0, 17, 19, 36], [1, 12, 24, 35], 8, G_{\lbrace5,6,7,8\rbrace}P_{10}=(x^{17}+1)(x^{19}+1)-x(x^{11}+1)(x^{13}+1)$

The Prohet-Tarry-Escott problem is to find disjoint sets (or multisets) $A,B$ with $\sum_{a \in A}x^i=\sum_{b \in B}x^i$ for $0 \le 1 \le q$ (and $|A|-q$ small). This is equivalent to $F_{AB}$ being divisible by $(x-1)^{q+1}.$ A solution of the form $G_S$ is called a pure product and many optimal soltions have this form up to additional factors. Notice that many of the solutions above have this property.

-
@AaronMeyerowitz: Many thanks for the detailed analysis. –  user24084 Jun 3 '12 at 5:20
The discrepancy of AP with respect to $S_1$ and $S_2$ is defined as $||S_1 \cap AP| - |S_2 \cap AP||$. –  user24084 Jun 3 '12 at 5:27
I found an interesting claim in book The Discrepancy Method'', Chazelle, Page 20, Theorem 1.11: Any two coloring of integers {1, ..., n} contains an arithmetic progression whose discrepancy is $\Omega(n^{1/4})$. The proof fixes common difference as $c\sqrt{n}$ (where $c$ is a constant). [Roth, Remark concerning integer sequences, Acta Arit., 1964] In the context of OP, for $m = n/2$, we get a bound on $k$ to be $c\sqrt{n}$. If this is the best bound then it implies that there always exists an equi-partition of {1,...,n} which are (multi-set) equivalent $\mod i$, for all $i < c\sqrt{n}$. –  user24084 Jun 3 '12 at 5:38
I am very intrigued, and my examples above do include some arithmetic progressions although not of size $m=\frac{n}{2}.$ But I do not see how the result you quote relates to the OP. –  Aaron Meyerowitz Jun 4 '12 at 2:10
Let $S_1$ and $S_2$ be two disjoint $\frac{n}{2}$ element subsets of {1,...,n}. Consider an arithmetic progression that starts with $a$ and with common difference $d$ having discrepancy with respect to $S_1$ and $S_2$ as claimed above. Then the count of $a \mod d$ in $S_1 \mod d$ will differ from $S_2 \mod d$ by at least $n^{1/4}$ ensuring that the multiset $S_1 \mod d$ is not equal to multiset $S_2 \mod d$. –  user24084 Jun 4 '12 at 4:23