A square with entries whose adjacencies never repeat

Question

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.)

Answer 1

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.

Answer 2

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$.