Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $X$ be a finite set of positive integers. Define $X$ mod $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$.

share|improve this question
2  
I think $k$ is a function of $A$ $B$, but does not only depend on $m$ and $n$. For example (with $n = 4$ and $m = 2$) if $A = \{1,3\}$ and $B = \{2,4\}$ then $k = 2$. But if $A = \{1,2\}$ and $B = \{3,4\}$, then $k = 3$. –  Joel Cohen May 27 '12 at 14:58
    
@JoelCohen: I guess that just proves that $k \geq 3$; I believe what the OP wants is a bound that would work for every pair of sets. OP, could you confirm that? –  Najib Idrissi May 27 '12 at 16:05
    
@N.I For $n\gt m=2$, the value then is $k=n$: if $1\lt k\lt n-1$, then $A=\{1,2\}$, $B=\{1,k+2\}$ are equal modulo $k$. And $A=\{1,2\}$ $B=\{2,n\}$ have $A\bmod n-1 = B\bmod n-1$. –  Arturo Magidin May 27 '12 at 17:50
    
@N.I.: Yes, I am looking for a bound that works for every disjoint pair with the same number of elements. –  K MathCS May 28 '12 at 0:42
    
@ArturoMagidin: Please note that the sets should be disjoint. Your examples do not satisfy the criterion. –  K MathCS May 28 '12 at 0:45
show 2 more comments

1 Answer

From the comments, I understand OP is interested in the case where each set has just one element, and we want the smallest $k$ such that for all $p,q$, $p$ and $q$ are incongruent modulo $k$. But that's easy: if $1\le p\lt q\le n$, then $p$ and $q$ are not congruent modulo $n$, and if $k\lt n$, then we can take $p=1$, $q=k+1$, getting $p$ and $q$ congruent modulo $k$. So in the $m=1$ case, the smallest $k$ is $n$. So perhaps the question has not been stated to reflect exactly what OP wants.

EDIT: I gather from the comment that OP has clarified (in a darker mood, I might say, shifted the goalposts again) and wants the maximum over all pairs $p,q$ (with $1\le p\lt q\le n$) of the minimum $k$ such that $p$ and $q$ are incongruent modulo $k$. The conjecture that $k=O(\log n)$ is correct. If $p$ and $q$ are congruent modulo $r$ for $r=1,2,3,\dots,s$ then they are congruent modulo the least common multiple $M$ of the numbers $1,2,3,\dots,s$, which means they differ by at least $M$, which means $n\ge M$. Now it is known that $M$ is asymptotically $e^s$ (see any text on analytic number theory), so $\log M=s+o(1)$. This gives what you want (for the case $m=1$).

share|improve this answer
    
For $p = 1$, $q = x$, if $x$ is even, $k = 2$. In the worst case, $k = O(log~ x)$. This is perhaps true in general too i.e. given two positive integers $p$ and $q$, where $1 \leq p \leq q \leq n$ there always exist a $k = O(log~ n)$ such that $p \not\equiv q ~mod~ k$. I do not have a proof. –  K MathCS May 28 '12 at 15:35
    
GerryMyerson: My apologies for the confusion. Thank you for giving proof for $m = 1$ case. Now for $m > 1$, does $k$ still remains $O(log~n)$. In this case, I am unable to conjecture any bound on $k$. –  K MathCS May 29 '12 at 2:27
    
Good question. For $m=1$, $n=2521$, we need $k=11$ to distinguish between 1 and 2521. But for $m=2$ and the much smaller $n=143$ we still need $k=11$ to distinguish between $\{{1,143\}}$ and $\{{71,73\}}$. I'd recommend doing small examples and looking for patterns. –  Gerry Myerson May 29 '12 at 3:16
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.