2
$\begingroup$

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

  • 0
    A specific case could be to consider to find $k$ for $p$, $q$ where 1 \leq p < q \leq n such that $p \not\equiv q ~mod~ k$. In other words, the size of sets $A$ and $B$ with just one element.2012-05-28

1 Answers 1

1

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

  • 0
    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.2012-05-29