Conjecture on strong nodal domains of ternary Hamming graphs

The conjecture fails for $n=5$. We construct an integer-valued eigenfunction of $H(5,3)$ with Laplacian eigenvalue $15$ and exactly four strong nodal domains. The function has 28 zero vertices; these are excluded from strong nodal domains, as required by the definition in Valyuzhenich–Vorob’ev, Sections 1–2 and Conjecture 2.

The eigenfunction

Write vertices as $x=(x_0,x_1,x_2,x_3,x_4)\in\{0,1,2\}^5$. Define two functions on $\{0,1,2\}$ by

$$\begin{aligned} (b_0(0),b_0(1),b_0(2))&=(1,0,-1),\\ (b_1(0),b_1(1),b_1(2))&=(0,1,-1). \end{aligned}$$

For $0\le j<32$, let $\epsilon_i(j)\in\{0,1\}$ be its binary digits, so that $j=\sum_{i=0}^4 2^i\epsilon_i(j)$. Specify the 32 integers $c_j$ by the following matrix, whose entry in row $r$ and column $s$ is $c_{8r+s}$, with rows and columns starting at zero:

$$\begin{pmatrix} 0&3&-7&0&1&0&4&1\\ -7&-1&3&0&1&1&0&0\\ 0&-6&-3&-1&4&0&-2&0\\ -1&0&1&2&4&1&1&-1 \end{pmatrix}.$$

Set

$$f(x)=\sum_{j=0}^{31}c_j \prod_{i=0}^4 b_{\epsilon_i(j)}(x_i).$$

This is nonzero: $f(1,0,0,0,0)=c_1=3$. Each $b_a$ sums to zero, so the sum of $f$ along every coordinate line is zero. Consequently, for each vertex $x$ and each coordinate, the values at the two neighbors obtained by changing that coordinate sum to $-f(x)$. There are five coordinates and every vertex has degree ten. Therefore

$$\begin{gathered} (Af)(x)=-5f(x),\\ (Lf)(x)=10f(x)-(Af)(x)=15f(x). \end{gathered}$$

This is also the usual tensor-product construction of eigenfunctions, recalled in Lemma 1 and Corollary 1 of the cited paper. No approximation of an eigenvalue or eigenvector is involved.

The four strong nodal domains

Let $P=\{x:f(x)>0\}$ and $N=\{x:f(x)<0\}$. Define

$$\begin{aligned} B=\{&(0,2,2,1,1),\ (1,2,2,1,1),\\ &(1,2,2,2,1)\}, \end{aligned}$$

and $C=\{(2,2,0,2,2)\}$. The values of $f$ on the three listed vertices of $B$ are respectively $5,2,5$, and its value on $C$ is $-17$. The four strong nodal domains are

$$P\setminus B,\quad B,\quad N\setminus C,\quad C,$$

with sizes $101,3,110,1$, respectively. There are exactly 28 remaining vertices, all with value zero.

Here is a complete exact verification of this finite certificate. It evaluates the displayed definition on all $3^5=243$ vertices. The neighbor routine uses precisely adjacency in $H(5,3)$. For each proposed domain it checks both connectedness and the absence of edges to another vertex with the same strict sign. All arithmetic is integer arithmetic.

from itertools import product

c = (
    0, 3, -7, 0, 1, 0, 4, 1,
    -7, -1, 3, 0, 1, 1, 0, 0,
    0, -6, -3, -1, 4, 0, -2, 0,
    -1, 0, 1, 2, 4, 1, 1, -1,
)
V = tuple(product(range(3), repeat=5))

def value(x):
    total = 0
    for j, coefficient in enumerate(c):
        term = coefficient
        for i, a in enumerate(x):
            if a == 2:
                term = -term
            elif a != ((j >> i) & 1):
                term = 0
        total += term
    return total

def neighbors(x):
    for i in range(5):
        for a in range(3):
            if a != x[i]:
                yield x[:i] + (a,) + x[i+1:]

F = {x: value(x) for x in V}
assert F[(1, 0, 0, 0, 0)] == 3
for i in range(5):
    for y in product(range(3), repeat=4):
        assert sum(F[y[:i] + (a,) + y[i:]]
                   for a in range(3)) == 0
for x in V:
    assert sum(F[x] - F[y] for y in neighbors(x)) == 15*F[x]

P = {x for x in V if F[x] > 0}
N = {x for x in V if F[x] < 0}
B = {(0, 2, 2, 1, 1), (1, 2, 2, 1, 1), (1, 2, 2, 2, 1)}
C = {(2, 2, 0, 2, 2)}
assert B <= P and C <= N
domains = (P - B, B, N - C, C)
assert [len(U) for U in domains] == [101, 3, 110, 1]
assert sum(F[x] == 0 for x in V) == 28

for U in domains:
    root = min(U)
    reached, pending = {root}, [root]
    while pending:
        x = pending.pop()
        for y in neighbors(x):
            if F[x]*F[y] > 0:
                assert y in U
                if y not in reached:
                    reached.add(y)
                    pending.append(y)
    assert reached == U

print("243 vertices; eigenvalue 15; 28 zeros; 4 strong nodal domains")

Thus $\mathrm{SND}(f)=4<6=n+1$, contradicting Conjecture 2.