8
$\begingroup$

Suppose we have an $n \times n$ square, and an alphabet $\Gamma$. We put an element of $\Gamma$ in each location of the square. An element can appear in more than one location. The constraint is that a pair $a,b$ of neighbors (either east-west of each other, or north-south of each other) can only appear in that configuration once.

Example of a prohibited square:

a b c
d e f
g d e

Since "de" appears on both the second and the third row, the entries of the square are not acceptable. The same problem would arise if, say, a appeared above d anywhere except the top left corner.

Given $n$, the width of the square as a parameter, what is a lower bound on the size of the alphabet $\Gamma$?

I would love (suggestions toward) a direct proof, but also, has this type of square-filling problem been studied? I can't connect it to either a Latin square, or a block design. Does this map onto any already-named combinatorial object?

(Note: this is related to a previous question of mine about avoiding partial words, but that question only required avoidance east-west, so to speak, whereas here I need to avoid north-south repetitions also.)

$\endgroup$
10
  • $\begingroup$ If I understand the question correctly, you do not prohibit “a” and “b” appearing in adjacent cells twice as long as the directions are different. Is this what you mean? $\endgroup$ Sep 30 '11 at 20:47
  • $\begingroup$ @Tsuyoshi: Yes. "ab" in one place, and "ba" in another is ok, including if they are on the same line, appearing as "aba." $\endgroup$ Sep 30 '11 at 20:53
  • $\begingroup$ As a side note, the only relevant reference I have been able to find is Latin Squares Which Contain no Repeated Digrams from 1965(!). I am reviewing that now, and it may have useful techniques, but I don't want to limit myself to Latin squares. $\endgroup$ Sep 30 '11 at 20:55
  • $\begingroup$ Do you already have some results for small values of $|\Gamma|$? For example, if $|\Gamma| = 3$, what is the largest possible $n$ that can be achieved? $\endgroup$ Sep 30 '11 at 20:58
  • $\begingroup$ @Jukka: Considering only the east-west no-repetition requirement, I can show that $|\Gamma| \geq n-2$ through a counting argument. I'm not sure how to approach adding in the north-south restriction also. I haven't worked small examples, but I can do that. $\endgroup$ Sep 30 '11 at 21:06
10
$\begingroup$

An extended version of my comment:

Let $p = n+1$ be a prime number. Then we can construct an $n \times n$ square from the multiplication table of integers modulo $p$. For example, if $p = 5$, we have

1234
2413
3142
4321

Now each pair $ab$ with $a \ne b$ occurs exactly once. Similarly, each pair $a$-above-$b$ with $a \ne b$ occurs exactly once.

Hence this is a valid construction; alphabet size $n$ and an $n \times n$ square.

Moreover, it is optimal. In an $n \times n$ square there are $n(n-1)$ horizontal pairs, and each of them must be different. If we had an alphabet of size $n-1$, we could only construct $(n-1)^2 < n(n-1)$ different horizontal pairs.

$\endgroup$
1
  • $\begingroup$ Thanks @Jukka, that's great. It isn't a full answer (as I know you know) because I would like to say something about "all $n$ sufficiently large" not just a set of $n$ with the density of the primes. I will think about extending your approach. $\endgroup$ Oct 1 '11 at 0:45
9
$\begingroup$

EDITED TO ADD: Gilbert's paper turns out to have historical importance, and it fully solves the problem I asked in my question. Please see my blog entry for more details.


ORIGINAL ANSWER

It turns out that the paper I found from 1965, Gilbert's Latin Squares Which Contain No Repeated Digrams, is quite helpful.

Using permutations with distinct differences, he constructs Latin squares of size $n$ for every even $n$, such that no adjacent pair ever repeats in the square, neither in rows nor columns. So $|\Gamma| \leq n+1$ in my question, because either the input parameter is even, or I can just add one to it, build the Latin square of size $n+1$, and then chop off one row and one column.

(A permutation with distinct differences is a permutation in which all the differences between consecutive elements are distinct. So, for example, on three elements, (1 3 2) is a permutation with distinct differences, since $3-1 \neq 2-3$, but (1 2 3) is not, since $2-1 = 3-2$.)

He later generalizes this in a way that relates to Jukka's answer. Suppose we want not just unique appearances of pairs $ab$, but of $a \lozenge^k b$, where $\lozenge$ is a "don't care" symbol, and $k$ ranges from 0 to $n-2$. That is to say, for a given $k$, there would be at most one occurrence of $a \lozenge^k b$ in the rows, and at most one in the columns, of the square. (This is a property that interests me a lot, by the way.) According to another theorem of Gilbert, it is possible to build a Latin square with such a property if $n+1=p$ where $p$ is prime.

So the question then becomes: given $n$, what is the least prime number larger than $n$? The Prime Number Theorem, etc., only give asymptotic bounds, but there are some explicit bounds known. The best one I have found is due to Dusart, Estimates of Some Functions Over Primes Without RH: for $x \geq 396738$, there is at least one prime in the interval $[x,x+ x/25 \ln^2 x]$. So, if we want to avoid repetition of pairs with don't-care symbols in between, asymptotically, for large enough $n$, $|\Gamma| \leq n + n/25\ln^2 n$.

$\endgroup$
2
  • $\begingroup$ Out of curiosity: Could you perhaps add some examples of the constructions for even $n$? $\endgroup$ Oct 2 '11 at 20:57
  • 1
    $\begingroup$ @Jukka: Yes. I might write a blog entry on this. I will either do that, or add to this answer, or both, over the next couple days. $\endgroup$ Oct 2 '11 at 21:21

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.