I tried to solve this by induction but wasn't successful. Problem is:

Determine the number of $(2^n -1) \times (2^n-1)$tables with 1 or -1 entries such that each entry is the product of neighboring entries. (Two entries are neighboring if they have an edge in common)

  • $\begingroup$ Which entries count as neighboring? Those that are adjacent vertically and horizontally? And what happens along the edges? $\endgroup$ Nov 7, 2013 at 17:44
  • 2
    $\begingroup$ The phrase "each entry is the product of four neighboring entries" is a little puzzling, since it's not clear what it means for edge or corner elements that don't have four neighboring entries. But we might suppose that these entries are the product of their two or three neighboring entries. Then it seems that the crucial observation is that just over half the entries can be chosen with no constraints at all, and that doing so completely constrains all the remaining entries. $\endgroup$
    – MJD
    Nov 7, 2013 at 17:44
  • $\begingroup$ @MJD You are right. "Four neighboring entries" should be replaced by "neighboring entries" as you explained. $\endgroup$ Nov 7, 2013 at 17:50
  • $\begingroup$ My idea above does not work. $\endgroup$
    – MJD
    Nov 7, 2013 at 18:14

1 Answer 1


Here is a partial answer : I make some computations that hold for every $n$, and I show that for $n=3$ there is only one solution, the trivial solution (all entries equal to $1$).

Let $M=(2^n-1)$. You are looking for the matrices $(t_{ij})_{1\leq i,j \leq M}$ satisfying your property.

It is easier to work additively than multiplicatively, so let $\phi : \lbrace -1,1 \rbrace \to {\mathbb F}_2$ be the isomorphism defined by $\phi(-1)=1$ and $\phi(1)=0$.

Then the matrix $S=(s_{ij})_{1\leq i,j \leq M}$ defined by $s_{ij}=\phi(t_{ij})$ satifies : for any entry $(i,j)$, $s_{ij}$ is the sum modulo $2$ of its neighbors. If we define a function $f: {\mathbb Z}^2 \to {\mathbb F}_2$ by $f(i,j)=s_{ij}$ if $1\leq i,j \leq M$ and $0$ otherwise, then we deduce

$$ f(i,j)=f(i-2,j)+f(i-1,j-1)+f(i-1,j)+f(i-1,j+1) (i,j \in {\mathbb Z}) \tag{1} $$

Let us put $g(j)=f(1,j)$ for $j\in {\mathbb Z}$. Using (1) with $i=2$, we have

$$ f(2,j)=g(j-1)+g(j)+g(j+1) \ \ (j \in {\mathbb Z}) \tag{2} $$

Using (1) with $i=3$ and combining it with (2), we see that

$$ f(3,j)=g(j-2)+g(j+2) \ \ (j \in {\mathbb Z}) \tag{3} $$

Continuing this way, we see by induction that there is for each $i$ a set $A_i \subseteq \mathbb Z$ such that for any $j$, $$ f(i,j)=\sum_{t\in A_i}g(j+t) \tag{4} $$

Here are some $A_i$’s :

$$ \begin{array}{lcl} A_1 &=& \lbrace 0 \rbrace \\ A_2 &=& \lbrace 0; \pm 1 \rbrace \\ A_3 &=& \lbrace \pm 2 \rbrace \\ A_4 &=& \lbrace 0; \pm 2; \pm 3 \rbrace \\ A_5 &=& \lbrace 0; \pm 2; \pm 4 \rbrace \\ A_6 &=& \lbrace 0; \pm 3; \pm 4; \pm 5 \rbrace \\ A_7 &=& \lbrace 0; \pm 6 \rbrace \\ A_8 &=& \lbrace 0; \pm 1; \pm 3;\pm 4; \pm 6\pm 7 \rbrace \\ \end{array} $$

There is no obvious pattern as far as I can see. Let us look at what happens when $n=3,M=7$ : by the value of $A_8$ above, one has

$$ \begin{array}{lclcl} 0 &=& f(8,1) &=& g(1)+g(2)+g(4)+g(5)+g(7) \\ 0 &=& f(8,2) &=& g(1)+g(2)+g(3)+g(5)+g(6) \\ 0 &=& f(8,3) &=& g(2)+g(3)+g(4)+g(6)+g(7) \\ 0 &=& f(8,4) &=& g(1)+g(3)+g(4)+g(5)+g(7) \\ 0 &=& f(8,5) &=& g(2)+g(4)+g(5)+g(6) \\ 0 &=& f(8,6) &=& g(3)+g(5)+g(6)+g(7) \\ 0 &=& f(8,7) &=& g(1)+g(4)+g(6)+g(7) \\ \end{array} $$

Solving the system, we see that all the $g(j) (1\leq j \leq 7)$ are zero, so that in that case there is only the trivial solution.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .