GEOMETRY, COMBINATORICS, AND ALGEBRA OF INDUCTIVELY PIERCED CODES

NEW

Problem: Conjecture 4.6 is naturally formalized as follows. Let $\mathcal C\subseteq 2^{[n]}$ be an inductively pierced neural code, labeled so neuron $i$ is introduced at step $i$. For nonempty codewords $c$, let $y_c\mapsto \prod_{i\in c}x_i$, and let $T_{\mathcal C}$ be the kernel. Order codewords by

$$c<d \iff \max c<\max d,$$

breaking ties by larger $|c|$ first, then lexicographically; let $\prec$ be the lexicographic term order with $y_c\prec y_d$ when $c<d$, as in Lienkaemper’s paper. The conjecture says $T_{\mathcal C}$ has a Gröbner basis of degree $\le 2$ with respect to $\prec$.

Result: The conjecture is false.

Take the full code

$$\mathcal C=2^{[6]}.$$

It is inductively pierced: starting with $2^{[1]}$, at step $i$ add neuron $i$ as an $(i-1)$-piercing with $\lambda=[i-1]$, $\sigma=\tau=\varnothing$, producing $2^{[i]}$.

In $T_{\mathcal C}$, consider

$$f = y_{1456}y_{2346}y_{136} - y_{1346}y_{3456}y_{126}.$$

Both monomials map to

$$x_1^2x_2x_3^2x_4^2x_5x_6^3,$$

so $f\in T_{\mathcal C}$.

Under $\prec$, among max-$6$ variables, smaller cardinality is larger, and for equal cardinality lexicographically later sets are larger. Hence $y_{136}\succ y_{126}$, so

$$LT_\prec(f)=y_{1456}y_{2346}y_{136}.$$

Its quadratic divisors are

$$y_{1456}y_{2346},\qquad y_{1456}y_{136},\qquad y_{2346}y_{136}.$$

Each is $\prec$-minimal among degree-$\le2$ monomials in its fiber:

• For $1456,2346$, alternatives are obtained by repartitioning $\{1,2,3,5\}$ over the fixed intersection $\{4,6\}$. Any unequal split gives a larger variable of smaller size; equal splits other than the original introduce $2456$ or $3456$, larger than $2346$.
• For $1456,136$, alternatives repartition $\{3,4,5\}$ over $\{1,6\}$. The original uses the smallest possible size-$3$ max-$6$ variable, $136$; alternatives use $146$ or $156$, or a still larger size-$2$ variable.
• For $2346,136$, alternatives repartition $\{1,2,4\}$ over $\{3,6\}$. Again $136$ is the smallest possible size-$3$ max-$6$ variable; alternatives use $236$ or $346$, or a larger size-$2$ variable.

Thus no leading term of any quadratic element of $T_{\mathcal C}$ divides $LT_\prec(f)$. Therefore no quadratic Gröbner basis exists with respect to $\prec$.

Citation: Conjecture and notation: Caitlin Lienkaemper, “Geometry, combinatorics, and algebra of inductively pierced codes,” arXiv:1811.04712, Conjecture 4.6. The counterexample above is given here.