7
$\begingroup$

Defining a word as sequence of ordered letters ($1$..$q$ letters) of length L, what is the minimal number of words such that among the entire list of words, at every pair of positions, I can find any two letters?

for example, for $q=3$ and $L=2$ here is the minimal list: $$1 1, 2 2, 3 3, 1 2, 2 3, 3 1, 1 3, 2 1, 3 2,$$ total $q^2$ words are needed.

but for $L=3$ the minimal number is still $q^2$, obtained by: $$1 1 1, 2 2 1, 3 3 1, 1 2 2, 2 3 2, 3 1 2, 1 3 3, 2 1 3, 3 2 3,$$

for $L=4$ the number is different...

what is the minimal number of words for $(q,L)$ and specifically, what is the asymptotic value for $L\gg 1$?

Thanks for you answers!

$\endgroup$
6
  • 2
    $\begingroup$ This is not research level and may be closed. Anyway what you want is an orthogonal array of strength $t=2$ and repetition $\lambda=1$ over a $q-$ary alphabet. This is an array of symbols from the alphabet, where looking down any two columns each possible pair of symbols appear once. There is a large literature on this subject. $\endgroup$
    – kodlu
    Commented Apr 24, 2020 at 0:36
  • 9
    $\begingroup$ @kodlu if there is a large literature, why is not it research level? $\endgroup$ Commented Apr 25, 2020 at 9:23
  • 7
    $\begingroup$ The OP's response to @kodlu's question indicates that the object in question is related to, but distinct from, orthogonal arrays. I think this question should get a fair shot at being answered rather than getting closed. $\endgroup$ Commented Apr 27, 2020 at 19:43
  • 1
    $\begingroup$ @FedorPetrov If I play devil's advocate, there is a large literature on computing derivatives of elementary functions too. $\endgroup$ Commented Apr 28, 2020 at 7:48
  • 3
    $\begingroup$ @NajibIdrissi true, and even more literature on unhappy love. But I guess the literature we did not all study at school is mentioned. At least I did not study these arrays. The question looks non-trivial and I would like to see the answer. $\endgroup$ Commented Apr 28, 2020 at 9:08

2 Answers 2

4
$\begingroup$

A Possible Solution: Actually given your family for $q=L=3,$ we can duplicate it (side by side) with the goal of achieving the goal for $L=6.$ Here, all $(i,j)$ with $i\leq 3,j\geq 4,\quad i\neq j\pmod 3$ positions will also achieve all 2-tuples by design.

So you can insert extra rows at the bottom with x incidating don't care to cover those $i,j$ in the left and right halves with $i=j \pmod 3.$ $$ \begin{array}{c} 111~111\\ 221~221\\ 331~331\\ 122~122\\ 232~232\\ 312~312\\ 133~133\\ 213~213\\ 321~321\\ \\ 111~222\\ 222~111\\ 111~333\\ 333~111\\ 222~333\\ 333~222\\ \end{array} $$ If I'm not missing something this gives a gain in efficiency.

Now recursively double the new full array, this will then require you covering some other pairs whose indices are the same mod 6.

Earlier Discussion: What you may use is an orthogonal array of strength $𝑡=2$ and repetition $\lambda=1$ over a $q−$ary alphabet. This is an array of symbols from the alphabet, where looking down any two columns each possible pair of symbols appear once ($\lambda=1)$.

The exactly once property is not necessarily needed for your purposes, but it yields constructions that are uniform with respect to the symbol pair positions. This may be natural feature of an optimal solution.

Hedayat and Sloane have a nice book on orthogonal arrays. The talk at the Isaac Newton institute, video and slides available here is a nice overview.

Rao’s and Bose-Bush’s bounds apply generally, but can be improved in special cases.

From page 10 of the slides, the general lower bound (translated into your variables with $N$ the number of rows) $$ N\geq L(q-1)+1 $$ can be obtained. Strengthening this in general is hard since the standard results rely on the condition $\lambda-1$ being nonzero modulo some parameter but your $\lambda=1.$

$\endgroup$
5
  • $\begingroup$ Thank you for a thorough answer! My question however is slightly different than what the answer would suggest. In the scenario that I describe, you don't have to have the same repetition of every pair. It merely requires the existence of every pair... $\endgroup$
    – Kleeorin
    Commented Apr 27, 2020 at 19:35
  • $\begingroup$ Also, that lower bound seems pretty weak to me. Given for example L=2, the minimal N for such an array is q^2 words. Given q>>2 this would make this bound entirely irrelevant, am I missing anything? Thanks again! $\endgroup$
    – Kleeorin
    Commented Apr 27, 2020 at 19:38
  • $\begingroup$ I do not understand your naive bound. Could you please elaborate? $\endgroup$ Commented Apr 28, 2020 at 8:21
  • 1
    $\begingroup$ @FedorPetrov, it was wrong, deleted. Should teach me not to post too late at night. $\endgroup$
    – kodlu
    Commented Apr 28, 2020 at 8:28
  • $\begingroup$ So, your answer asymptotically provides about $q(q-1)\log_2L$, right? $\endgroup$ Commented May 3, 2020 at 22:29
2
$\begingroup$

First, let me elaborate the upper bound from @kodlu’s answer. If $q$ is a power of a prime, then $q^2$ words suffice for $L=q+1$ (for $L=q$ it is almost trivial, improving by $1$ needs just a bit more). Then, doubling $L$ increases the number of words by $q(q-1)$, so for those values of $L$ it suffices to take $q(q-1)\log_2\frac L{q+1}+q^2$ words.

Let me show a somewhat close lower bound. Let $w$ be the number of words; set $k=w-q(q-1)+1$. Take any $k$ words. Let $v_i$ be a vector composed from all $i$th entries of the $k$ words. If two of those vectors, say $v_i$ and $v_j$, coincide, this means that at most $w-k=q(q-1)-1$ words differ in positions $i$ and $j$, so not all pairs are covered.

Thus, we have $L$ distinct vectors in $[q]^k$, so $L\leq q^k$, or $w\geq q(q-1)+1+\log_qL$.

Therefore, the growth rate is indeed logarithmic (but the constant at the logarithm is yet unclear).

Addendum. Let me present an example for $L=q+1$, when $q$ is a power of a prime.

Consider an affine plane $\mathbb F_q^2$. All lines in it are partitioned into $q+1$ classes $C_1,\dots,C_{q+1}$ of mutually parallel lines (one class consists of all lines with equations of the form $ax+by=c$ with fixed $(a:b)$). Enumerate the lines in each class by numbers from 1 to $q$.

For each point $p\in \mathbb F_q^2$, take a word $w_1\dots w_{q+1}$ where $w_i$ is the number of the line in $C_i$ passing through $p$. Then, for any two classes $C_i$ and $C_j$ and for any two lines in them, the lines meet at a unique point, which means exactly what we need to get in the $i$th and $j$th positions.

$\endgroup$
4
  • $\begingroup$ The base of logarithm can be improved to $q-1$ (for $q>2$ by looking at $k=w-q(q-1)+1+2t$ vectors and saying they should differ in at most $2t+1$ positions. But the improvement is not that large... $\endgroup$ Commented May 4, 2020 at 13:39
  • $\begingroup$ Thank you! Could you clarify "for 𝐿=𝑞 it is almost trivial" ? $\endgroup$
    – Kleeorin
    Commented Jun 11, 2020 at 17:06
  • $\begingroup$ I’ve added an example even for $L=q+1$. $\endgroup$ Commented Jun 11, 2020 at 18:52
  • $\begingroup$ BTW, a ‘trivial’ example I meant consists of all arithmetic all progressions module $q$, if $q$ is prime. $\endgroup$ Commented Jun 11, 2020 at 19:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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