What is the name of this combinatorial object and place to read about it?

Question

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.

Answer 1

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.