Every element of $A$ and $B$ differ in at least $k$ positions

Question

Let $m,n$ be positive integers, $m,n>1$ and $X = \{(x_1,x_2, ..., x_m) \in \mathbb{Z}^m :1 \le x_i \le n, \forall 1 \le i \le m\}$.

$A$ and $B$ are two disjoint subsets of $X$, such that if $a \in A$ and $b \in B$ then $a$ and $b$ differ in at least $k$ positions (i.e. $a=(a_1,a_2, ..., a_m)$, $b=(b_1,b_2, ..., b_m)$ and there are at least $k$ values $i$ such that $a_i \ne b_i$).

What conditions should $|A|$ and $|B|$ satisfy?
Given that there are positive integers $r, s$ satisfying $|A| \ge r$ and $|B| \ge s$, what is the miminimum value $n$ could have as a function of $k,m,r,s$?

For example, let $m=2$, $X = \{(x_1,x_2) \in \mathbb{Z}^2 :1 \le x_i \le n, \forall 1 \le i \le 2\}$.
If $k=1$ then the relation $|A|+|B| \le n^2$ is sharp.
If $k=2$ it's not hard to see that the following relation holds and it's sharp: $\sqrt{|A|} + \sqrt{|B|} \le n$ (note that if $A_{1}$ is the set of the possible values for $a_1$, and defining $A_2$, $B_1$, $B_2$ in the same way, one has $|A_1|+|B_1| \le n$ and $|A_2|+|B_2| \le n$, where $|A| \le|A_1||A_2|$ and $|B| \le|B_1||B_2|$).

However the problem becomes significantly harder even for $m=3$.

Does anyone know any reference where this problem has been studied or know how to proceed in the general case?
I'm interested on any known results, even for small values of $m$, such $m=3$ or $m=4$.

Answer 1

Here is a construction. Let $m=m_a+m_b,$ where you can choose $m_a\geq 1$ and $m_b\geq 1$ as you wish and consider $\mathbb{Z}^m=\mathbb{Z}^{m_a} \times \mathbb{Z}^{m_b}.$

First work over $\mathbb{Z}_2.$ Choose $k=k_a+k_b$ as the number of coordinates that you want the length $m$ codewords to be different. Define two binary codes as $$ C_a=\{(v|| \mathbb{0} ): w_H(v)\geq k_a\} $$ where $||$ denotes concatenation, and note that you have $2^{m_a}-V_{k_a-1}(m_a)$ codewords in $C_a$ where $V_r(\ell)$ denotes the volume of the binary Hamming sphere of radius $r$ in $\ell$ dimensions. This volume can be approximated by the entropy function depending on the ratio $k_a/m_a,$ if you wish, asymptotically. For example, it is easy to see that if $k_a\approx m_a/2$ you can have $|C_a|\gg 2^{m_a}.$ A similar argument can be used for $C_b$ defined below: $$ C_b=\{( \mathbb{0}||u ): w_H(u)\geq k_b\} $$ So the concatenated binary code $C_2 \subset \mathbb{Z}_2^m$ given by $C_a \times C_b$ has $\gg 2^{m},$ codewords asymptotically.

Now even if you confine yourself to bounded integers, $\mathbb{Z} \bigcap [0,2v],$ you can use the above code and its translates by 2, say $$ C_{\mathbb{Z}}=\bigcup_{j=1}^v (C_2+2j) $$ to get an even larger code. Here we use the notation $C_2+2j=\{c+(2j,2j,\ldots,2j): c \in C_2\}.$

It seems to me choosing $m_a=\lfloor m/2 \rfloor,$ may be optimal in the sense of getting the largest code, for a given $v.$

Old Answer for Reference:

Note that there may be a better way of doing this, but your question can be addressed within coding theory as below.

I will use $d$ instead of $k$ (coding theory notation). Take any $[n,k,d]$ linear code $C$ over $GF(q).$ So you will be restricted to prime powers for your $m=q,$ and thus $|C|=q^k.$

You can then use the known bounds on these parameters, Hamming, Singleton, Gilbert Varshamov etc.

Decompose $C=A \cup B,$ where $A \cap B=\emptyset.$ Then try to optimize whatever measure $\alpha |A|^a+\beta |B|^b,$ or similar by selecting $|A|,$ since $|B|=q^k-|A|.$

In fact, since the code is linear, all its translates $C_u=C+u$ are distinct (let $C_0=C,$ and each will satisfy the same distance properties as a set. If $d$ is much smaller than $n,$ then translating by a vector $u$ of Hamming weight greater than $d$ will enable you to use the above approach and decompose $C_u \cup C_0,$ improving your parameters with respect to these bounds.

For the binary alphabet, you can try to use set systems with controlled symmetric differences from design theory, taking your vectors to be the characteristic functions of those sets.