<p>An extended version of my comment:</p>

<p>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</p>

<pre><code>1234
2413
3142
4321
</code></pre>

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

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

<p>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 &lt; n(n-1)$ different horizontal pairs.</p>

CC BY-SA 3.0
2011-10-01T00:45:38.710Z
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.
Aaron Sterling
CC BY-SA 3.0
2011-09-30T21:47:27.027Z
2011-09-30T22:00:58.993Z
2011-09-30T22:00:58.993Z
Jukka Suomela
<p><strong>EDITED TO ADD</strong>:  Gilbert's paper turns out to have historical importance, and it fully solves the problem I asked in my question.  Please see <a href="http://nanoexplanations.wordpress.com/2011/10/09/an-independent-discovery-of-costas-arrays/" rel="nofollow">my blog entry</a> for more details.</p>

<hr>

<p><strong>ORIGINAL ANSWER</strong></p>

<p>It turns out that the paper I found from 1965, Gilbert's <a href="http://www.jstor.org/stable/2027267" rel="nofollow">Latin Squares Which Contain No Repeated Digrams</a>, is quite helpful.</p>

<p>Using <em>permutations with distinct differences</em>, 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.</p>

<p>(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$.)</p>

<p>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.</p>

<p>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, <a href="http://arxiv.org/abs/1002.0442" rel="nofollow">Estimates of Some Functions Over Primes Without RH</a>: 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$.</p>

CC BY-SA 3.0
2011-10-02T20:57:15.703Z
Out of curiosity: Could you perhaps add some examples of the constructions for even $n$?
Jukka Suomela
CC BY-SA 3.0
2011-10-02T21:21:29.037Z
@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.
Aaron Sterling
CC BY-SA 3.0
2011-10-02T20:06:34.293Z
2011-10-10T19:57:16.367Z
2011-10-10T19:57:16.367Z
Aaron Sterling
<p>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.</p>

<p>Example of a prohibited square:</p>

<p>a b c<br>
d e f<br>
g d e  </p>

<p>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. </p>

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

<p>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?</p>

<p>(Note: this is related to a <a href="https://cstheory.stackexchange.com/q/7865/30">previous question</a> 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.)</p>

CC BY-SA 3.0
2011-09-30T20:47:49.410Z
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?
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-30T20:53:18.563Z
@Tsuyoshi: Yes.  "ab" in one place, and "ba" in another is ok, including if they are on the same line, appearing as "aba."
Aaron Sterling
CC BY-SA 3.0
2011-09-30T20:55:00.073Z
As a side note, the only relevant reference I have been able to find is [Latin Squares Which Contain no Repeated Digrams](http://www.jstor.org/stable/2027267) from 1965(!).  I am reviewing that now, and it may have useful techniques, but I don't want to limit myself to Latin squares.
Aaron Sterling
CC BY-SA 3.0
2011-09-30T20:58:48.587Z
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?
Jukka Suomela
CC BY-SA 3.0
2011-09-30T21:06:23.730Z
@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.
Aaron Sterling
CC BY-SA 3.0
2011-09-30T21:22:29.693Z
can the same letter appear next to itself? Like $aa$?
Artem Kaznatcheev
CC BY-SA 3.0
2011-09-30T21:24:51.720Z
What if you just take the multiplication table of integers modulo a prime number?
Jukka Suomela
CC BY-SA 3.0
2011-09-30T21:26:07.333Z
@Artem yes.  (This is an example of what makes it different from a Latin square.)
Aaron Sterling
CC BY-SA 3.0
2011-09-30T21:32:45.997Z
@everyone: thank you all for your rapid interest.  I have to be away from the computer for a while, so I won't be able to comment again for a few hours.  Thanks again.
Aaron Sterling
CC BY-SA 3.0
2011-10-01T06:00:04.447Z
A related problem is Seth Pettie's work on forbidden submatrices: http://www.eecs.umich.edu/~pettie/papers/FH-J.pdf
Suresh Venkat
<co.combinatorics>
A square with entries whose adjacencies never repeat
Aaron Sterling
# A square with entries whose adjacencies never repeat

(Asked by: username_0 on 2011-09-30)

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](https://cstheory.stackexchange.com/q/7865/30) 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.)

**Tags:** co.combinatorics

> **Comments:**
> **username_1**: 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?  
> **username_0**: @Tsuyoshi: Yes.  "ab" in one place, and "ba" in another is ok, including if they are on the same line, appearing as "aba."  
> **username_0**: As a side note, the only relevant reference I have been able to find is [Latin Squares Which Contain no Repeated Digrams](http://www.jstor.org/stable/2027267) from 1965(!).  I am reviewing that now, and it may have useful techniques, but I don't want to limit myself to Latin squares.  
> **username_2**: 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?  
> **username_0**: @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.  
> **username_3**: can the same letter appear next to itself? Like $aa$?  
> **username_2**: What if you just take the multiplication table of integers modulo a prime number?  
> **username_0**: @Artem yes.  (This is an example of what makes it different from a Latin square.)  
> **username_0**: @everyone: thank you all for your rapid interest.  I have to be away from the computer for a while, so I won't be able to comment again for a few hours.  Thanks again.  
> **username_4**: A related problem is Seth Pettie's work on forbidden submatrices: http://www.eecs.umich.edu/~pettie/papers/FH-J.pdf  

---

## 2 answers

### Answer by username_0 on 2011-10-02. Score: 9 | Accepted answer

**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](http://nanoexplanations.wordpress.com/2011/10/09/an-independent-discovery-of-costas-arrays/) for more details.

---

**ORIGINAL ANSWER**

It turns out that the paper I found from 1965, Gilbert's [Latin Squares Which Contain No Repeated Digrams](http://www.jstor.org/stable/2027267), 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](http://arxiv.org/abs/1002.0442): 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$.

> **Comments:**
> **username_2**: Out of curiosity: Could you perhaps add some examples of the constructions for even $n$?  
> **username_0**: @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.  

---

### Answer by username_2 on 2011-09-30. Score: 10

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.

> **Comments:**
> **username_0**: 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.  

---

