Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
I looked a bit at the case $m=2$ at mathoverflow.net/questions/98529/… –  Gerry Myerson Jun 1 '12 at 0:17
add comment

1 Answer

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.

share|improve this answer
    
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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