27
$\begingroup$

The title is admittedly noninformative but I could not figure out how to squeeze into it the description of the object I am interested in. Judge by yourself.

I have an alphabet on $d$ symbols. I want to build a rectangular array with $pd$ rows and $qd$ columns filled with them in such a way that each row contains $p$ copies of each symbol, each column contains $q$ copies of each symbol, and the following number $n$ is minimized.

For each pair $i,j$ of columns, let $n_{ij}$ be the number of rows where these columns contain identical symbols. Then $n$ is the largest of the $n_{ij}$ for all $i\ne j$.

I cannot even figure out what is the smallest possible value of $n$ for given $d,p,q$.

I tried to search for such structures. Not that I did not find anything. On the contrary, I found too many very similar investigations around gadgets called block designs, association schemes, Steiner triples and whatnot. Unfortunately I was unable to find the thing I need - I do not even give it a name since I am sure it already has a well-established name but I cannot figure out what it is.

$\endgroup$
  • $\begingroup$ Can you say a little about the context or motivation? $\endgroup$ – Todd Trimble Nov 26 '16 at 16:10
  • $\begingroup$ @ToddTrimble hmm I am not sure it is interesting since it is a "very applied" motivation. There are $d$ identically structured tests with $pd$ items each, all different, which must be rearranged into $qd$ tests by repeatedly using items ($q$ times each item from each test), and it is desired that the new tests have as few common items as possible. $\endgroup$ – მამუკა ჯიბლაძე Nov 26 '16 at 16:14
  • 8
    $\begingroup$ If $p=q=1$ then $n=0$ and this is the well studied notion of Latin Square. So I guess these are generalized latin squares... ;) sorry I can't help more. $\endgroup$ – Abdelmalek Abdesselam Nov 26 '16 at 16:56
  • 5
    $\begingroup$ @AbdelmalekAbdesselam Thanks a lot, this is much closer than anything I found before! Two papers from 1980 on Generalized Latin rectangles by Andersen and Hilton are almost what I need - their conditions are $\leqslant p$ and $\leqslant q$ where I need exactly $p$ and $q$, and they do not minimize anything, but they have lots of interesting ideas about it, and I can find further papers citing them. $\endgroup$ – მამუკა ჯიბლაძე Nov 26 '16 at 17:16
  • $\begingroup$ I am glad that my comment was useful after all :) $\endgroup$ – Abdelmalek Abdesselam Nov 26 '16 at 17:17
38
$\begingroup$

What you're asking for is a code with two non-usual restrictions. It's a code over alphabet size $d$. You want each code word to have length $pd$ and you want to have $qd$ total code words.

The parameter you call $n$ is equal to $pd - \Delta$, where $\Delta$ is called the distance of your code. You want to minimize $n,$ which is the same as maximizing the distance $\Delta.$

So far, your set-up is exactly the same as the usual set-up in coding theory, and this problem is extremely well-studied. You add the two additional restrictions that

  1. If we project onto any given coordinate, then each symbol should appear equally often (this is not really much of a restriction since we could take linear codes when say $d$ is a prime power); and

  2. Each code word needs to use each symbol the same number of times (this is much more of a restriction, I'd say).

In either event, if you want to get the best possible bounds, consider say the Hoffman bound (an upper bound on codes not needing to satisfy your additional 1 and 2). Then consider a suitable random code, which you need to make sure has property 2 by construction. Then it will almost have property 1, so make sure to save a few code words at the end so that you can fix this. Then hopefully this random code will match the Hoffman bound decently well.

Another thought is to look at say Reed-Solomon codes.

The case $d=2$ is very, very well-studied (binary codes), and I wouldn't be surprised if your problem is known in that setting.

Added:

In fact, it seems this has been studied. Condition 2 is called "balanced codes" (or more generally constant weight codes). They have applications to bar codes and such, apparently. See here.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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