NEURAL IDEALS AND STIMULUS SPACE VISUALIZATION

arXiv:1607.00697v1 [q-bio.NC] 3 Jul 2016

ELIZABETH GROSS, NIDA KAZI OBATAKE, AND NORA YOUNGS

Abstract. A neural code C is a collection of binary vectors of a given length n that
record the co-firing patterns of a set of neurons. Our focus is on neural codes arising from
place cells, neurons that respond to geographic stimulus. In this setting, the stimulus
space can be visualized as subset of R2 covered by a collection U of convex sets such that
the arrangement U forms an Euler diagram for C. There are some methods to determine
whether such a convex realization U exists; however, these methods do not describe how
to draw a realization. In this work, we look at the problem of algorithmically drawing
Euler diagrams for neural codes using two polynomial ideals: the neural ideal, a pseudomonomial ideal; and the neural toric ideal, a binomial ideal. In particular, we study how
these objects are related to the theory of piercings in information visualization, and we
show how minimal generating sets of the ideals reveal whether or not a code is 0, 1, or
2-inductively pierced.

1. Introduction
In 2014, the Nobel Prize in Medicine or Physiology was awarded to John O’Keefe and
his team for their 1971 discovery of place cells [22]. A place cell is a neuron that codes
a distinct region in an animal’s environment called a place field. That is, if the animal
is in a place field, the associated place cell fires; otherwise it is silent. Such neurons are
believed to be an essential part of the navigation system and spatial memory.
The firing activity of a population of neurons over time results in a set of co-firing patterns, which can be stored using binary vectors, or codewords. Each codeword indicates
the set of neurons that were firing together during some time window. A set C ⊂ {0, 1}n
of codewords on n neurons is called a combinatorial neural code; the descriptor “combinatorial” is commonly used since the precise details of neural spiking and timing are
discarded, leaving only discrete co-firing patterns. For a description of how neuronal firing
data may be discretized, see [6].
Each codeword in a combinatorial neural code C is associated with the set of neurons
it represents; that is, given c ∈ C ⊂ {0, 1}n , we associate c with Zc := supp(c) = {i ∈
[n] | ci = 1}. If the neurons in question are known to be place cells, then a codeword c of
co-firing place cells indicates that the neurons in Zc have overlapping place fields.
Place fields can be approximated by convex sets in R2 , for example, see [5, Figure 1].
Given an arrangement of convex subsets of R2 representing place fields, we can easily
extract the associated neural code by considering the various zones in the arrangement.
That is, given a collection of sets U = {U1 , ..., Un } with each Ui ⊂ R2 a convex set, the
code associated to U is
\  [ 
C(U) = {c ∈ {0, 1}n |
Ui \
Uj 6= ∅},
i∈Zc

1

j ∈Z
/ c

2

ELIZABETH GROSS, NIDA KAZI OBATAKE, AND NORA YOUNGS

as illustrated in Figure 1. We define
neuron i.

T

i∈∅

Ui = R2 and refer to Ui as the place field of

Figure 1. An arrangement of three sets U = {U1 , U2 , U3 }; the codeword
associated to the shaded region is c = 110 and Zc = supp(c) = {1, 2}. Here,
the associated code is C(U) = {000, 100, 010, 110, 101, 111}.
The inverse problem is more difficult: given a particular neural code C presumed to
come from place cells, can we find a set of convex subsets in R2 which would, as place
fields, exhibit C as its associated code? If such a collection of convex sets exists, the code
is called convexly realizable in R2 . Previous work [8, 5] has considered the question of
determining whether or not a neural code is convexly realizable in R2 from the viewpoint
of convex geometry and algebraic topology. Once it is determined that a code is convexly
realizable, however, it is not yet known how to algorithmically construct a realization.
Since a neural code can be viewed as a set of relationships between n sets, realizations
of neural codes are Euler diagrams, which have been studied since the 1700’s [17]; Venn
diagrams are examples of Euler diagrams. Thus the motivating question at the center of
this work is: Given a neural code, how does one draw its corresponding Euler diagram?
While Euler diagrams using convex sets can occasionally be drawn by hand with some
creativity, drawing Euler diagrams using convex sets automatically has been challenging.
However, techniques have been proposed in the field of information visualization [12], [2],
[26], [27], including one particularly efficient method using the theory of piercings [28].
Specifically, in [28] Stapleton et al. give a polynomial time algorithm to draw a realization
using circles if the code is inductively pierced. We give a precise definition of inductively
pierced in Section 2, however we note here that 0, 1, and 2-inductively pierced codes are
simple to intuit. For example, a code is 1-inductively pierced if there exists a realization
using circles that can be drawn iteratively, where at each step a closed curve is added
with the condition that the new curve can intersect at most one previously drawn curve.
The existence of such a drawing algorithm as the one in [28] means that experimentalists
can produce stimulus space visualizations of inductively pierced codes. Thus, in this
paper, we focus on connecting the theory of piercings to computational algebraic geometry
and developing techniques for checking whether a code is k-inductively pierced. This
follows the footsteps of algebraic statistics [23, 11], which has used tools from commutative
algebra and algebraic geometry to look at problems in computational biology for the past
decade and a half. We take an ideal theoretic focus, examining two ideals, the neural
ideal, a pseudo-monomial ideal, and the toric ideal of a neural code, a binomial ideal.
The neural ideal and its canonical form were first introduced in [8], and have been used
to answer questions regarding the place field structure of a neural code, including set

NEURAL IDEALS AND STIMULUS SPACE VISUALIZATION

3

n

relationships [8] and convexity [5]. For a code C ⊂ {0, 1} , the neural ideal JC is defined
as follows:
Y Y
JC = h
xi
(1 − xj ) | v ∈ {0, 1}n \Ci ⊆ F2 [x1 , ..., xn ]
vi =1

vj =0

In [8], the authors show that the pseudo-monomials in the neural ideal correspond to
set containments in realizations of the code:
Proposition 1.1. [8, Lemma 4.2] Q
If {U1 , ...,

Q Un } is a collection of sets with corresponding
T
code C, then the pseudo-monomial i∈σ xi j∈τ (1 − xj ) is in JC if and only if
Ui ⊆
i∈σ
S
j∈τ Uj .
This relationship between the neural ideal and place field structures lends itself naturally to answering questions regarding automatically drawing realizations. In Section 3,
we make this connection concrete by giving necessary conditions on the canonical form
for k-inductively pierced codes, and necessary and sufficient conditions on the canonical
form for 0- and 1-inductively pierced codes. Once it is determined that a code is inductively pierced, then the algorithm for automatically drawing Euler diagrams developed
by Stapleton et al. [28] may be applied to draw a place field diagram for the neural code.
In addition to the neural ideal and its canonical form, there are other algebraic objects
that can aid in place field visualization; in this manuscript, we introduce toric ideals of
neural codes. In general, toric ideals are binomial ideals which have been well studied due
to their underlying combinatorial structure [21] and their expansive list of applications,
including categorical data analysis [10], network modeling [24], evolutionary biology [31],
systems biology [3], integer programming [30], geometric modeling [4], and mathematical
physics [1].
A toric ideal is most commonly defined in terms of an integer matrix, however, for this
application, we will define it in terms of the neural code. The connection to the standard
definition of a toric ideal is straightforward, since we can treat each codeword as a column
in an n × m matrix. Let C = {c1 , . . . , cm } be a neural code on n neurons and define φC as
follows:
φC : K[pc | c ∈ C \ {00 . . . 00}] −→ K[xi | i ∈ {1, . . . , n}]
Y
pc 7−→
xi .
i∈supp(c)

The toric ideal of C, denoted IC , is the kernel of the map φC .
The advantage of working with toric ideals is that there is software available (e.g. 4ti2
[35]) for working with these particular type of ideals that is interfaced with both Sage [29]
and Macaulay2 [16]. Thus performing computations is straightforward and fast when n is
reasonable. For example, finding the generators for a toric ideal of a code on 50 neurons
consisting of 75 codewords took 0.059 seconds on a 2015 MacBook Air with a 2.2 GHz
Intel Core i7 processor.
In Section 4, we give degree bounds on the generators of IC when C is 0 or 1-inductively
pierced. In fact, the toric ideals associated to 1-inductively pierced codes form a class of
toric ideals generated by quadratics, and thus these ideals would be interesting to study
from a purely combinatorial commutative algebra viewpoint.

4

ELIZABETH GROSS, NIDA KAZI OBATAKE, AND NORA YOUNGS

In order to prove the main theorems from Section 4, we rely on the fact that toric ideals
arising from 0-1 matrices are toric ideals of hypergraphs, which have been studied in [32],
[25], and [15]. In fact, we use the machinery for establishing degree bounds in [15] to give
the degree bound in Theorem 4.5.
The paper is organized as follows. Section 2 focuses on the basic definitions and notation
that provide the foundation for this paper. In Section 2, we introduce Euler diagrams,
k-piercings, and formally define what it means for a code to be k-inductively pierced. We
also introduce the neural ideal and its canonical form and toric ideals of neural codes.
We close Section 2 by reviewing the needed theory on toric ideals of hypergraphs. In
Section 3, we show how to detect k-piercings from the canonical form of the neural ideal,
describe the canonical form structure of k-inductively pierced codes, and give necessary
and sufficient conditions for 0- and 1-inductively pierced codes using the neural ideal.
We end Section 3 by giving an algorithm for finding piercing orderings for 1-inductively
pierced codes using the canonical form. In Section 4, we show that a neural code is 0inductively pierced if and only if its toric ideal is the zero ideal. We then show that the
toric ideal of a 1-inductively pierced code is generated by quadratics and give preliminary
evidence for a stronger conjecture regarding 1-inductively pierced codes. In Section 5,
we conclude by working through an example of a neural code with 17 neurons and 28
codewords using the methods described in Sections 3 and 4.
2. Definitions and Notation
2.1. Euler diagrams and k-inductively pierced codes. Let C ⊂ {0, 1}n be a code
on n neurons. We will assume C contains the all-zeros word and all neurons fire at least
once, that is, for each i ∈ [n], there is at least one codeword c ∈ C with ci = 1. In other
words, we are assuming all place fields are non-empty.
An Euler diagram d for n sets is a collection of n labeled simple, closed curves (λ1 , λ2 ,
. . . , λn ) in R2 . The interior of the curve λi is a subset Ui of R2 , i.e. Ui = int λi . Denoting
the boundary of Ui as ∂Ui , we have that λi = ∂Ui . Non-empty intersections of the sets
U1 , . . . , Un and their complements
Ū1 , . . .T
, Ūn form regions called zones; specifically, a set
T
Z is a zone in diagram d if ( i∈Z Ui ) ∩ ( j ∈Z
/ Ūj ) is nonempty. An Euler diagram is said
to be well-formed [28] if it satisfies the following conditions:
(1) Each curve label is used only once.
(2) All curves intersect generally (so curves intersect in finitely many points.)
(3) A point in the plane is passed through at most 2 times by the curves in the
diagram.
(4) Each zone is connected.
Because we will focus on well-formed Euler diagrams in this manuscript and wellformedness requires each curve label to be used only once, we will use λi to denote both
the ith curve and the label of the ith curve. We call a diagram convex if each Ui = intλi
is convex.
An abstract description D = (L, Z) of an Euler diagram d is an ordered pair specifying
the curve labels L and the zones Z ⊆ P(L), where P(L) denotes the power set of L. We
will assume ∅ ∈ Z and if λ ∈ L, then there exists a Z ∈ Z such that λ ∈ Z. We will call
an Euler diagram d with abstract description D a realization or drawing of D.

NEURAL IDEALS AND STIMULUS SPACE VISUALIZATION

5

n

Let c ∈ {0, 1} and Zc = supp c ⊆ [n]. A neural code C on n neurons corresponds
naturally to the abstract description DC = ([n], ZC ) where ZC = {Zc : c ∈ C}. We call an
abstract description D well-formed if there exists a well-formed realization of D, and we
call a code C well-formed if DC is well-formed.
We now describe two subsets of the power set P(L) that will be used in the definition
of a k-piercing of an abstract description. Let D = (L, Z) be an abstract description.
Given λ ∈ L, let Xλ ⊂ Z be the set of all zones that contain λ:
Xλ = {Z ∈ Z : λ ∈ Z}.
Given Z ∈ Z and Λ ⊂ L such that Z ∩ Λ = ∅, let the Λ-cluster of Z, denoted YZ,Λ be
the set:
YZ,Λ = {Z ∪ Λi : Λi ⊆ Λ}.
Definition 2.1. [28] Let D = (L, Z) be an abstract description. Let Λ = {λ1 , ..., λk } ⊆ L
be distinct curve labels. Then λk+1 ∈ L is a k-piercing of Λ in D if there exists a zone Z
such that
(1) λi ∈
/ Z for each i ≤ k + 1
(2) Xλk+1 = YZ∪{λk+1 },Λ , and
(3) YZ,Λ ⊆ Z.
When the above conditions hold, we say that λk+1 is a k-piercing identified by the background zone Z.
As we will focus primarily on 0- and 1-piercings in this paper, we now give a more
detailed description and example of each type.
Example 2.2 (0-piercings). A 0-piercing is a curve that intersects zero other curves in
the diagram. Let D = (L, Z) be an abstract description. Then λ is a 0-piercing in D if
there exists a zone z such that λ ∈
/ Z, Xλ = {Z ∪ {λ}}, and Z ∪ {λ} ∈ Z.
As an
example
of
a
0-piercing,
let
C = {000, 100, 010, 101}. Then
n
o

DC =
1, 2, 3 , ∅, {1}, {2}, {1, 3} , and the label “3” is a 0-piercing in DC identified
by the zone Z100 = {1}. Figure 2a illustrates the 0-piercing in terms of a place field
diagram of C.

1

1

2

2
3

3

(a) A diagram with a 0-piercing.

(b) A diagram with a 1-piercing.

Figure 2. Examples of piercings.

6

ELIZABETH GROSS, NIDA KAZI OBATAKE, AND NORA YOUNGS

Example 2.3 (1-piercing). A 1-piercing intersects exactly one other curve in the diagram.
Consider the diagram d pictured in Figure 2b. The
 abstract description D for this diagram
has curve labels L = {1, 2, 3} and zones Z = ∅, {1}, {2}, {1, 2}, {2, 3}, {1, 2, 3} . Curve
3 is a 1-piercing of curve 1 identified by the zone {2} ∈ Z since
(1) 3, 1 ∈
/{2},

(2) X3 = {2, 3}, {1, 2, 3} = ({2} ∪ {3})
 ∪ Λi | Λi ⊆ {1} = Y{2}∪{3},{1} , and
(3) Y{2},{1} = {2} ∪ Λi | Λi ⊆ {1} = {2}, {1, 2} ⊆ Z.
It should be noted that intersecting exactly one other curve is not sufficient to indicate a
1-piercing; in this example, curve 2 only intersects curve 1, but curve 2 is not a 1-piercing.
In terms of drawings, we can think of a k-piercing as a curve that pierces k other curves
and splits 2k zones. These 2k zones appear in the abstract description in the following
way.
Lemma 2.4. Let D = (L, Z) be an abstract description. Let Λ = {λ1 , ..., λk } ⊆ L be
distinct curve labels. If λk+1 ∈ L is a k-piercing of Λ in D then there exist exactly 2k
elements of Z that contain λk+1 , i.e. |Xλk+1 | = 2k .
Proof. The statement follows from the second condition in the definition of a k-piercing.

In order to define what it means for an abstract description to be k-inductively pierced,
we need to discuss the removal of piercing curves in terms of the abstract description.
Definition 2.5 (Removal of a curve). Given an abstract description D = (L, Z) with
λ ∈ L, then we define
D − λ = (L \ {λ}, Z − λ),
where Z − λ = {Z \ {λ} : Z ∈ Z}.
When C is a neural code, we can similarly discuss the removal of a neuron. We define
C − λ = {(c1 , . . . , cλ−1 , ĉλ , cλ+1 , . . . , cn ) : (c1 , . . . , cn ) ∈ C}.
If we consider C as a n × m matrix, where m = |C|, then we can obtain C − λ by deleting
the λth row.
Definition 2.6. An abstract description D = (L, Z) is k-inductively pierced if D has a
0-, 1-, . . . , or k-piercing λ such that D − λ is k-inductively pierced. We will call a code C
k-inductively pierced if its abstract description DC is k-inductively pierced.
Since we will be focused on diagrams drawn entirely with circles, we will restrict our
attention to 0-, 1-, and 2-inductively pierced descriptions (a 3-piercing cannot occur in
R2 if all curves must be circles). In [28], the authors introduce a subclass of 2-inductively
pierced descriptions, called inductively pierced. They show that if D is an inductively
pierced abstract description, then there exists a drawing d of D, composed entirely of
circles, which can be drawn in polynomial time. Note that 2-inductively pierced is a
weaker requirement on an abstract description than inductively pierced as defined in [28].
Inductively pierced, however, implies 2-inductively pierced.
We end this section by noting that well-formed diagrams with no intersecting curves
have 0-inductively pierced descriptions.

NEURAL IDEALS AND STIMULUS SPACE VISUALIZATION

7

Proposition 2.7. Let D be well-formed. An abstract description D is inductively 0pierced if and only if all curves in any well-formed realization of D do not intersect.
Proof. Suppose D is inductively 0-pierced. Assume for the sake of contradiction that there
exists a well-formed realization d of D such that there exist two curves, λ1 and λ2 , that
intersect. Since D is 0-inductively pierced, we can remove 0-piercings until λ1 or λ2 is a
0-piercing of the remaining curves, thus, without loss of generality, let us assume λ1 is a
0-piercing of D. Condition (2) of Definition 2.1 implies that there exists a zone Z, with
corresponding codeword z, such that the curve λ1 is contained entirely in ∩i∈Z Ui . Thus,
we can zoom in on this crossing as illustrated in Figure 3.
00z
p

λ1
10z

λ2
01z

11z

Figure 3. A closeup of a crossing of curves λ1 and λ2 .
From Figure 3, we see that |Xλ1 | ≥ 2. But since λ1 is a 0-piercing, by Lemma 2.4, there
exists exactly 20 = 1 element of Z that contains λ1 , so |Xλ1 | = 1, a contradiction.
For the converse, let D be a well-formed abstract description. Suppose for any wellformed realization d of D, no two curves intersect. We will proceed by induction on n,
the number of curves/curve labels. The statement holds for n = 1, since the only code on
one neuron is 0-inductively pierced. Now suppose the statement holds for n ≤ r, and let
n = r + 1. Since none of the curves λ1 , . . . , λn intersect, every pair of place fields Ui and
Uj in d are either disjoint or nested. Select a minimal field with respect to set inclusion,
that is, select a place field Uk such that for all 1 ≤ i ≤ n with i 6= k either Ui ∩ Uk = ∅
or Uk ⊂ Ui ; note that since n is finite and D is well-formed, such a place field must exist.
Then λk is a 0-piercing of D, and by the induction hypothesis, D − λk is 0-inductively
pierced. Therefore, D is 0-inductively pierced.

2.2. The neural ideal and its canonical form. As discussed in the Introduction, we
will aim to identify k-inductively pierced codes using computational algebraic geometry.
One way the neural code has been approached with an algebreo-geometric lens is through
the neural ring and neural ideal [8]. To a given vector v ∈ {0, 1}n , we associate an
indicator polynomial ρv ∈ F2 [x1 , ..., xn ] such that ρv (v) = 1 and ρv (v 0 ) = 0 when v 0 6= v.
The indicator polynomial is constructed as follows:
Y Y
ρv =
xi
(1 − xj )
vi =1

vj =0

8

ELIZABETH GROSS, NIDA KAZI OBATAKE, AND NORA YOUNGS

For example, if n = 3 and v = 101, then ρv = x1 x3 (1−x2 ). The indicator
ρv is
Q polynomial
Q
a particular example of a pseudo-monomial, a polynomial of the form i∈σ xi j∈τ (1−xj )
where σ ∩ τ = ∅. Note that all monomials are necessarily pseudo-monomials by taking
τ = ∅. For a given ideal I, we consider a pseudo-monomial f to be minimal in I if there
are no pseudo-monomials g ∈ I and 1 6= h ∈ F2 [x1 , ..., xn ] such that f = gh; that is, f is
not a nontrivial multiple of another pseudo-monomial in I.
For any code C we define the neural ideal JC as follows:
JC = hρv | v ∈ {0, 1}n \Ci
Note that for any f ∈ JC , we have f (c) = 0 for all c ∈ C, i.e. all polynomials in JC
vanish on C, but for any v ∈
/ C, there is at least one polynomial g ∈ JC with g(v) 6= 0
and so C is precisely the variety of JC . Since considering the full list of generators ρv is
often inefficient and opaque, we consider instead the canonical form of the neural ideal,
CF (JC ), defined to be the set of minimal pseudo-monomials in JC . For more about the
neural ideal and the canonical form, see [8].
For our purposes, the most important property of the canonical form is its interpretation
in terms of an arrangement of sets which realize the code in question. We will make
substantial use of the previously stated Proposition 1.1(Lemma 4.2 from [8]), which states
that pseudo-monomials in JC are in direct correspondence with set-theoretic information
about the associated arrangement of sets U through the relation
Y Y
\
[
xi (1 − xj ) ∈ JC ⇔
Ui ⊆
Uj .
i∈σ

j∈τ

i∈σ

j∈τ

Q

T
When τ = ∅, this translates to i∈σ xi ∈ JC if and only if i∈σ Ui = ∅. Since we always
assume the all-zeros word is in the code, JC will never contain a pseudo-monomial with
σ = ∅.
Importantly, these relationships hold regardless of the arrangement which is chosen.
That is, since the canonical form and the ideal JC are properties of the code itself and not
of
arrangement U for which CT= C(U), the
Q the particular
Q
S presence of the pseudo-monomial
i∈σ xi
j∈τ (1 − xj ) in JC indicates that
i∈σ Ui ⊆
j∈τ Uj in any arrangement U for
which C = C(U).
Beyond being minimal pseudo-monomials and often a condensed generating set for
JC , the pseudo-monomials in CF (JC ) provide a minimal description of the interactions
between the sets Ui .
Example 2.8. Let C = {000, 100, 010, 101}, the code from Example 2.2. In this case, the
canonical form is
CF (JC ) = {x1 x2 , x2 x3 , x3 (1 − x1 )}.
Using Proposition 1.1, the elements give us the following place field relationships: U1 ∩
U2 = ∅, U2 ∩ U3 = ∅, and U3 ⊆ U1 . While U1 ∩ U2 ∩ U3 = ∅ is also true, corresponding
to the fact that x1 x2 x3 is also in JC , the information U1 ∩ U2 = ∅ implies the former fact
and hence it is redundant information.
2.3. The toric ideal of a neural code. The second algebraic object we will study
is the toric ideal of C. Let C = {c1 , . . . , cm } be a neural code on n neurons and let
C ∗ := C \ {00 . . . 00}, i.e. C ∗ is C with the all zeros word removed. Let K be a field and

NEURAL IDEALS AND STIMULUS SPACE VISUALIZATION

9

∗

let φC : K[pc | c ∈ C }] −→ K[xi | i ∈ {1, . . . , n}] be the polynomial ring homomorphism
defined by
Y
pc 7−→
xi .
i∈supp(c)

Recall that IC , the toric ideal of C, is the kernel of the map φC . From standard results on
toric ideals, the ideal IC is a prime ideal generated by binomials [30].
Example 2.9. Let C = A1 = {100, 010, 001, 110, 101, 011, 111}, a neural code on 3 neurons. We are using labeling of codes consistent with [7]. A place field diagram for this code
is pictured in Figure 4a. The toric ideal of this code IC ⊂ K[p100 , p010 , p001 , p110 , p101 , p011 , p111 ]
is generated by the following cubic and quadratics: p111 −p100 p010 p001 , p110 −p100 p010 , p101 −
p100 p001 , and p011 − p010 p001 .
Example 2.10. Let C = A2 = {100, 010, 110, 101, 111}, a neural code on 3 neurons. A
place field diagram for this code is pictured in Figure 4b. The toric ideal of this code IC
is:
IC = hp111 − p010 p101 , p110 − p100 p010 i.

1

2

1

2
3

3
(a) A place field diagram of A1

(b) A place field diagram of A2

Figure 4. Examples of place field diagrams of neural codes on three neurons
Toric ideals have a nice combinatorial structure. To visualize the information gathered
from the toric ideal and to aid in proofs, we introduce the notion of a hypergraph, which
is a generalization of a graph where edges can contain any number of vertices, not just
two. Toric ideals associated to hypergraphs have been studied in [32, 34, 25].
Definition 2.11. A hypergraph H is a pair H = (V, E) where V is a set of elements called
nodes or vertices, and E is a set of non-empty subsets of V called hyperedges or edges.
A code C on n neurons containing m codewords can be visualized as a hypergraph with
n vertices and m hyperedges.
Definition 2.12 (Hypergraph of a neural code). Given a code C ⊂ {0, 1}n , the hypergraph associated to C is HC = (V, E) where V = {1, . . . , n} and E = {Zc | c ∈ C ∗ }.

10

ELIZABETH GROSS, NIDA KAZI OBATAKE, AND NORA YOUNGS

Every edge in HC corresponds to an indeterminate in K[pc | c ∈ C ∗ }], and a collection,
or multiset, of edges in HC corresponds to a monomial. In order to encode a binomial of
the form pu − pv , composed of a monomial pu with a positive sign and a monomial pv of
a negative sign, we introduce edge colorings - specifically, bicolorings.
Definition 2.13 (Bicoloring of a multiset of edges [34]). Let E be a multiset of edges
from H. Partition E into two sub-multisets such that the multiset union of the two submultisets is equal to E. Assign one color to each sub-multiset, say blue and red. Then
E = (Eblue , Ered ) = (B, R), where B is the set of blue edges and R is the set of red edges.
Such a coloring of E is called a bicoloring of E.
Definition 2.14 (Balanced edge set [25]). Let E = (B, R) be a multiset of bicolored
edges from H = (V, E). For v ∈ V , let degB v be the number of edges in B that contain
v, counted with multiplicity. Define degR v similarly. We say that E = (B, R) is balanced
with respect to the given bicoloring if for all v ∈ V
degB v = degR v.
If E is balanced, we call E a balanced edge set in H.
We say a binomial fE arises from E if it can be written as
Y
Y
pe 0 .
pe −
fE =
e0 ∈Ered

e∈Eblue

Every binomial in IC arises from a balanced edge set in the hypergraph HC in this manner
(see [25] and [15]).
Definition 2.15 (Primitive balanced set [15]). A balanced edge set E = (B, R) is primitive with respect to H if there does not exists another balanced edge set E 0 = (B 0 , R0 ) in
H such that B 0 ( B and R0 ( R.
Primitive balanced edge sets in HC correspond to primitive binomials in IC . A binomial
0
0
0
0
p − pv ∈ IC is primitive if there exists no other pu − pv ∈ IC such that pu |pu and pv |pv .
In particular, since IC is prime, primitivity of a binomial pu − pv ∈ IC implies the supports
of pu and pv are disjoint. The set of all primitive binomials is a generating set of IC , thus,
the set of all binomials arising from primitive balanced edge sets of HC generate IC .
u

Example 2.16. As an example, consider the code C = B1={000, 100, 010, 001, 110, 011}.
We can visualize the information from C using the hypergraph illustrated in Figure 5.

1

2

3

Figure 5. Hypergraph of neural code B1
By coloring the edges in the hypergraph, we see that there are at least two balanced
edge sets: each of vertex 1 and vertex 2 are contained in a single blue edge and in a

NEURAL IDEALS AND STIMULUS SPACE VISUALIZATION

11

single green edge. The blue edge around vertex 1 corresponds to the codeword 100, the
blue edge around vertex 2 corresponds to the codeword 010, and the green edge around
vertices 1 and 2 corresponds to the codeword 110. Additionally, each of the vertices 2 and
3 are contained in a single blue edge and in a single blue edge. In this case, the red edge
corresponds to the codeword 011. The generators of the toric ideal of B1 can be read off
the diagram as p110 − p100 p010 and p011 − p010 p001 .
Since hypergraphs combinatorially encode binomials in IC , we can obtain a degree
bound on a minimal generating set of IC by noting special properties of HC .
Definition 2.17. Let E = (B, R) be a balanced edge set of H. Let Γ1 and Γ2 be
balanced edge sets of H. A multiset S with support in H is a proper splitting set of E
with decomposition (Γ1 , S, Γ2 ) if S = Γ1red ∩ Γ2blue , S 6= Γ1red , Γ2blue , E ∪ S = (Γ1 ∪ Γ2 ) \ S,
and the following coloring conditions hold Γ1blue , Γ2blue ⊆ B ∪ S and Γ1red , Γ2red ⊆ R ∪ S.
Remark. When we are working with multisets, as in this section, we will interpret ∪, ∩,
and ⊆ in terms of their multiset definitions as described in Section 2 of [34].
We use the following degree bound theorem in Section 4.
Theorem 2.18. [15, Theorem 5.1] Let C be a code with corresponding hypergraph HC .
The toric ideal IC is generated by quadratics if for every primitive balanced edge set E of
HC with |Eblue | ≥ |Ered | and |Eblue | = n > 2, there exists a proper splitting set S of E with
decomposition (Γ1 , S, Γ2 ) where |Γiblue |, |Γired | < n for i = 1, 2.

3. The Neural Ideal and the Theory of Piercings
Stapleton et al. [28] show that not all codes are inductively pierced and give some
immediate “red flags” that show a curve is not a piercing of any others. Under our
algebraic interpretation, we find that the effect of a k-piercing on the canonical form of the
neural ideal is very predictable, and thus it is possible to detect algorithmically whether or
not a particular code has any piercings. Detecting whether a code is k-inductively pierced
is more complicated, since it requires us to find an ordering on the elements. However,
if only 0- and 1-piercings are used, we are able to algebraically detect inductive piercings
and determine a possible ordering using the canonical form of the neural ideal.
We first address the issue of simply detecting whether a k-piercing is present at all. We
can directly translate the three conditions from Definition 2.1 into set containment rules,
and thus directly into canonical form language, obtaining the following result:
Proposition 3.1. λk+1 is a piercing of λ1 , ..., λk identified by Z if and only if the following
hold:
(1) λi ∈
/ Z for 1 ≤ i ≤ k + 1
(2) (a) xλk+1 xQ
i ∈ CF (JC ) for all i ∈ [n]\(Z ∪ {λ1 , ..., λk+1 })
(b) xλk+1 i∈σ xi ∈
/ CF (JC ) for all σ ⊆ {λ1 , ..., λk }
(c) xλk+1 (1 − xj ) ∈ CF (JC ) for all j ∈ Z
(3) If we reduce the canonical form by setting xi = 0 for i ∈ [n]\(Z ∪ {λ1 , ..., λk+1 })
and setting xj = 1 for all j ∈ Z, we obtain only zeros.

12

ELIZABETH GROSS, NIDA KAZI OBATAKE, AND NORA YOUNGS

The translation of the definition of k-piercing into the language of the canonical form
follows from prior work [8]; note that the numbered conditions here match the numbered
conditions from Definition 2.1. When k, {λi }, λk+1 , and Z are known, it is not a difficult
matter to check the above conditions. However, even if none of this information is known
a priori, we can still determine if the code has piercings by checking each λ in turn.
To check if a particular λ is a piercing, we consider the polynomials in CF (JC ) which
involve λ. Let A be the set of indices a such that xλ xa is in CF (JC ), and let Z be the set
of indices j such that xλ (1 − xj ) is in CF (JC ); as CF (JC ) is a canonical form, A and Z are
disjoint. Then set B = [n]\(A ∪ Z). Set k = |B|, arbitrarily order B as B = {λ1 , ..., λk },
and check the conditions above. If they hold, then λ is a k-piercing of B within the zone
Z. If they do not, then λ is not a piercing of any curves in any zone. Note that by the
conditions necessary in Proposition 3.1, particularly condition (2), the possible zone Z
and the curves B which are pierced by λ are uniquely determined.
We now consider the special case of 0- and 1- piercings. As we will show, a 0-inductively
pierced code has a canonical form of a very specific kind: the relationship between two
place fields Ui and Uj is either disjointness (xi xj ∈ CF (JC )) or containment in a unique
direction (either xi (1 − xj ) or xj (1 − xi ) are in CF (JC ), but not both, as this would imply
equality of Ui and Uj which is impossible in a well-formed code).
Following the language in [28] and our previous discussion, recall that a code is 0inductively pierced if C has a 0-piercing λ such that C − λ is 0-inductively pierced. In
particular, the only 0-inductively pierced code on 1 neuron is {0, 1}. If C has a 0-piercing
λ, then this means that there is a codeword c ∈ C and a background zone Z such that
if cλ = 1 then supp(c) = Z ∪ {λ} (intuitively, Uλ is properly contained within zone Z in
any diagram).
Lemma 3.2. If λ is a 0-piercing for a code C, then C can be obtained from C−λ by adding a
neuron which is always 0, and then adding a codeword v such that supp(v) = supp(c)∪{λ}
for some c ∈ C.
Proof. Suppose λ is a 0-piercing of C, and Zc is a zone such that the definition holds. This
implies that we have the three conditions listed in Example 2.2. Thus, a code C with a
0-piercing λ is a code where all codewords except c have cλ = 0, and there is exactly one
codeword whose support is identical to c except at λ.

Similarly, translating the definitions of 1- and 2-piercing, we have the following results:
Lemma 3.3. If λ is a 1-piercing of {λ1 } for a code C, then C can be obtained from C − λ
by adding a neuron which is always 0, and then adding two codewords: one whose support
is supp(c) ∪ {λ} for some c ∈ C, and one whose support is supp(c) ∪ {λ, λ1 }.
Lemma 3.4. If λ is a 2-piercing of {λ1 , λ2 } for a code C, then C can be obtained from
C − λ by adding a neuron which is always 0, and then adding four codewords: one whose
support is supp(c)∪{λ} for some c ∈ C, and then codewords with support supp(c)∪{λ, λ1 },
supp(c) ∪ {λ, λ2 }, and supp(c) ∪ {λ, λ1 , λ2 }.
For each of these cases, we can translate these operations into changes in the canonical
form, as shown in the following result.

NEURAL IDEALS AND STIMULUS SPACE VISUALIZATION

13

Theorem 3.5. Let C be a code on n neurons. Then, the following three statements hold:
(1) If λ is a 0-piercing at zone z, then
CF (JC ) = CF (JC−λ ) ∪ {xi xλ | i ∈ [n]\(z ∪ {λ})} ∪ {xλ (1 − xj ) | j ∈ z}
(2) If λ is a 1-piercing of {λ1 } at zone z, then
CF (JC ) = CF (JC−λ ) ∪ {xi xλ | i ∈ [n]\(z ∪ {λ, λ1 })} ∪ {xλ (1 − xj ) | j ∈ z}
(3) If λ is a 2-piercing of {λ1 , λ2 } at zone z, then
CF (JC ) = CF (JC−λ ) ∪ {xi xλ | i ∈ [n]\(z ∪ {λ, λ1 , λ2 })} ∪ {xλ (1 − xj ) | j ∈ z}
The particular details of how changes in the canonical form reflect changes to the code
are discussed at length in [9]; in our case, the change is the removal of a neuron whose
place field pierces k others. This leads to the following property of the canonical form of
a k-inductively pierced code and a characterization of 0-inductively pierced codes.
Theorem 3.6. Let C be a code on n neurons.
(1) If C is k-inductively pierced, then the CF (JC ) ⊆ {fij | 1 ≤ i < j ≤ n, fij ∈
{xi xj , xi (1 − xj ), xj (1 − xi )}}.
(2) C is 0-inductively pierced if and only if CF (JC ) = {fij | i, j ∈ [n], i < j, fij ∈
{xi xj , xi (1 − xj ), xj (1 − xi )}.
Proof. Both (1) and the forward direction of (2) follow immediately by induction from
Theorem 3.5, and the fact that the only k-inductively pierced code on 1 neuron is C =
{0, 1}, which has empty canonical form.
To see the reverse direction of (2), we proceed by induction on n. If n = 1, then
CF (JC ) = ∅ so C = {0, 1}, which is 0-inductively pierced. Now, let n > 1, and assume
the result holds for n − 1. We will show that there is some λ so that CF (JC−λ ) is also
in the desired form, and that λ is a 0-piercing of C. To do this, pick λ which maximizes
|Bλ |, where Bλ = {i | xλ (1 − xi ) ∈ CF (JC )} (this choice may not be unique). Let B = Bλ ,
and let vB be the vector with supp(vB ) = B. To see that λ is a 0-piercing of C, we will
show that both vB and vB∪λ ∈ C, and that if c ∈ C with cλ = 1, then supp(c) = {λ} ∪ B.
First, to show that vB and vB∪λ are in C, we will show that for each fij ∈ CF (JC ), we
have fij (vB ) = fij (vB∪λ ) = 0. We have two cases:
(Case 1: fij = xi xj ). If either i or j is not in B ∪ λ, then fij (vB ) = fij (vB∪λ ) = 0.
We will show that any options where both i and j are in B ∪ λ is impossible. If both
i and j are in B, then xλ (1 − xi ) and xλ (1 − xj ) are both in CF (JC ). But then xλ =
xλ (1 − xi ) + xi (xλ (1 − xj )) + xλ (xi xj ) ∈ JC which is a contradiction. If i ∈ B and j = λ,
then xλ (1 − xi ) ∈ CF (JC ), which is a contradiction since we can’t have both xλ (1 − xi )
and fiλ = xλ xi in CF (JC ). A similar argument holds for i = λ and j ∈ B. Thus, any
case where i and j are both in B ∪ {λ} is impossible.
(Case 2: fij = xi (1 − xj )). If i ∈
/ B ∪ {λ}, then clearly fij (vB ) = fij (vB∪λ ) = 0. If
i = λ, then j is necessarily in B by definition, and hence fij (vB ) = fij (vB∪λ ) = 0. Finally,
if i ∈ B, then j 6= λ as we cannot have both xλ (1 − xi ) and xi (1 − xλ ) in CF (JC ) by the
presumed format. Thus, in this case, (1−xj )(xλ (1−xi ))+xλ (xi (1−xj )) = xλ (1−xj ) ∈ JC ,
and as neither xλ nor 1 − xj may be in JC , we have xλ (1 − xj ) ∈ CF (JC ), and hence j ∈ B.
So again fij (vB ) = fij (vB∪λ ) = 0.

14

ELIZABETH GROSS, NIDA KAZI OBATAKE, AND NORA YOUNGS

Now, suppose by way of contradiction that there is some cλ = 1 but supp(c) 6= {B ∪
{λ}}. If i ∈ B but ci 6= 1, then xλ (1 − xi ) could not be in JC as c would not evaluate to 0
on it, but we know xλ (1 − xi ) is in the canonical form by definition of B. So this cannot
occur. Thus, supp(c) 6= {B ∪ {λ}} must imply supp(c) ) B ∪ {λ}. Let i ∈ supp(c) and
i∈
/ B ∪ {λ}. For every j ∈ B, we know xi xj ∈
/ CF (JC ), and if xj (1 − xi ) ∈ CF then
i ∈ B so we must have xi (1 − xj ) ∈ CF (JC ). Furthermore, xi (1 − xλ ) ∈ CF (JC ) also, as
xλ (1 − xi ) and xi xλ cannot be. So λ was not a maximum choice which is a contradiction.
This shows that λ is indeed a 0-piercing of C; i.e., cλ = 0 for all codewords except one,
and that one is a copy of v otherwise. When we delete neuron λ, we obtain CF (JC−λ ),
which by [9] contains exactly the elements of CF (JC ) which did not involve xλ ; hence
each pair will occur exactly once and thus CF (JC−λ ) will have the desired format.

From these results, we see that it is possible to detect whether a code is 0-inductively
pierced by using the canonical form. We now move on to detecting whether a code is
1-inductively pierced. Recall that a code C is 1-inductively pierced if either C = {0, 1}, or
there is some 0- or 1-piercing λ such that C − λ is 0 or 1-inductively pierced.
For a given code C, we define the general relationship graph G(C) to have vertices
V = [n], and an edge {i, j} appears if and only if none of xi xj , xi (1 − xj ) and xj (1 − xi )
appear in CF (JC ). That is, G(C) connects two vertices exactly when there is no interesting
relationship (disjointness, containment) between their respective place fields.
Example 3.7. Let C = {00000, 10000, 11000, 10100, 11100, 01000, 00010, 01010, 01011}.
The canonical form for this code is CF (JC ) = {x1 x4 , x1 x5 , x3 x4 , x3 x5 , x3 (1 − x1 ), x5 (1 −
x2 ), x5 (1 − x4 )}. The general relationship graph G(C) places an edge between those pairs
that do not appear together in an element in the canonical form; here, those edges are
{1, 2}, {2, 3}, {2, 4}. See Figure 6 for an Euler diagram for this code and a drawing of
G(C).
(a)

1
3

2

4

(b)

1

2

4

5
3

5

Figure 6. (a) Euler diagram for the code C. (b)The general relationship
graph G(C).
Theorem 3.8. C is 1-inductively pierced if and only if CF (JC ) consists only of degree
two pseudo-monomials meeting the following conditions:
(i) For each pair {i, j}, at most one of xi xj , xi (1 − xj ), xj (1 − xi ) appears in CF (JC ).
(ii) G(C) is a forest.

NEURAL IDEALS AND STIMULUS SPACE VISUALIZATION

15

Corollary 3.9. C is 0-inductively pierced if and only if C is 1-inductively pierced and
G(C) consists only of isolated vertices.
This follows by Theorem 3.6.
Proof. First, we show the conditions are necessary. By Theorem 3.6, any 1-inductively
pierced code has a canonical form with only degree-two polynomials using each pair i, j
at most once, so condition (i) follows. Condition (ii) follows by induction: the only 1inductively pierced code on 1 neuron is {0, 1} and the graph of this code is a single vertex.
If λ is a 0- or 1-piercing of C and C − λ is 1-inductively pierced, then G(C − λ) is a forest
by induction. If λ is a 0-piercing, then by Theorem 3.5, CF (JC ) will contain a pair xλ xj
or xλ (1 − xj ) for every element j ∈ [n] − λ, plus the relationships in CF (JC−λ ), so G(C)
is obtained from G(C − λ), by adding an isolated vertex λ. If λ is a 1-piercing of λi ,
then again by Theorem 3.5, CF (JC ) will have a pair xλ xj or xλ (1 − xj ) for every element
j ∈ [n] − {λ, λi }. so G(C) is obtained from G(C − λ) by adding a vertex λ, and adding
single edge connecting λ with λi , so G(C) is also a forest.
To show these two conditions are sufficient, we proceed by induction on n. For n =
1, then the only code which has no degree 1 terms in its canonical form is the code
{0, 1}, whose canonical form is empty. In this case, condition (i) is trivially satisfied, and
G({0, 1}) an isolated vertex, so the code meets meets condition (ii). This code is trivially
1-inductively pierced.
Now, let C be an arbitrary code on n vertices meeting the required conditions. We will
show that there is some vertex λ of G(C) with degree ≤ 1 such that xj (1 − xλ ) does not
appear in CF (JC ) for any j ∈ [n]\{λ}. Once we prove that such a λ must exist, we will
show that it is either a 0 or 1 piercing of C; furthermore, that C − λ meets the required
conditions and hence by induction C − λ is 1-inductively pierced.
First, we prove that such a λ must exist. Let L be the set of elements of [n] which
have degree ≤ 1 in G(C); since G is a forest and n ≥ 2, L contains at least two elements.
Suppose by way of contradiction that for every element ` ∈ L there is some i ∈ [n] such
that xi (1−x` ) ∈ CF (JC ). We will show there is some `0 ∈ L with x0` (1−x` ) ∈ CF (JC ). To
do so, we will follow a path in G(C) starting from i of vertices j with xj (1 − x` ) ∈ CF (JC ),
until we reach a leaf. If i ∈ L, then we’re done. If not, then i has degree ≥ 2, and so if i and
` are connected in G(C), the degree of i allows us to move along a path away from G(C)
towards any leaf; if they are not connected, we may move along any path towards any leaf.
Let {i, j} be the first edge along this path. Note that {j, `} is not an edge, by our choice of
path. Hence, one of x` xj , x` (1 − xj ), or xj (1 − x` ) is in CF (JC ). If x` xj ∈ CF (JC ), then we
know xi (x` xj ) + xj (xi (1 − x` )) = xi xj ∈ CF (JC ), but this is a contradiction as {i, j} is an
edge. If x` (1−xj ) ∈ CF (JC ), then (1−xj )[xi (1−x` )]+xi [x` (1−xj )] = xi (1−xj ) ∈ CF (JC ),
again a contradiction as {i, j} is an edge. So it must be the case that xj (1−x` ) ∈ CF (JC ).
Repeating this as many times as necessary as we follow the path, we will eventually
arrive at a leaf `0 with x0` (1 − x` ), and thus find another element `0 of L with x0` (1 − x` ).
Since L is finite, repeating this leaf-finding process gives a list `1 , `2 , ..., `k of vertices with
each of `i (1 − `i+1 ) and `k (1 − x`1 ) appearing in CF (JC ). Since for any triple i, j, k, where
xi (1 − xj ) and xj (1 − xk ) ∈ CF (JC ), we have xi (1 − xk ) ∈ CF (JC ), we then obtain that

16

ELIZABETH GROSS, NIDA KAZI OBATAKE, AND NORA YOUNGS

`1 (1 − xk ) ∈ CF (JC ) as well as x`k (1 − x1 ), and this contradicts condition (i). Thus, such
a λ must exist.
Now, given such a λ, since has degree ≤ 1 in G(C), there is at most one λi which there
is no degree-2 polynomial involving λ and λi . If there is none, then by condition (i), λ is
a 0-piercing. If there is exactly one, λ is a 1-piercing of λi .
Finally note that by Theorem 3.5, the canonical form CF (JC−λ ) is exactly CF (JC )
with any term involving λ removed; such a canonical form will still have only degree-2
pseudo-monomials and condition (i) will still be met. Furthermore, G(C − λ) is just G(C)
with λ deleted since no other edges are affected, so G(C − λ) is a forest, so condition (ii) is
still met. Thus, by induction, C − λ is 0 or 1-inductively pierced and the result holds. 
The proof of the reverse implication above is quite powerful. Not only does it show
that 1-inductively pierced codes can be detected, it actually gives us a way to determine
a sequence (λ1 , . . . , λn ) of curve labels such that λi is a 0 or 1 piercing of DC−λi+1 −···−λn ,
which we will call a drawing order. Formalizing the algorithm, we determine a possible
drawing order as follows:
Algorithm 3.10.
Input: CF (JC ) and G(C) meeting conditions (i) and (ii).
Output: an 1-inductively pierced drawing order for C.
Step 0: Initialize an empty list L.
Step 1: Find a vertex ` in G(C) such that no pseudo-monomial of the form xj (1 − x` )
is present in CF (JC ), and deg(`) ≤ 1.
Step 2: Set L = (`, L).
Step 3: If |L| = n, stop. Otherwise, set C = C − `, recompute CF (JC ) and G(C), and
return to Step 1.
Note that this algorithm will serve to give an acceptable ordering even if the code is
0-inductively pierced. Section 5 contains an example of a drawing order outputted from
the above algorithm.
We believe similar results can be continued to k-inductively pierced codes, as in the
following conjecture:
Conjecture. A code is k-inductively pierced if and only if CF (JC ) consists only of degree
two pseudo-monomials meeting the following conditions:
(i) For each pair {i, j}, at most one of xi xj , xi (1 − xj ), xj (1 − xi ) appears in CF (JC ).
(ii) G(C) is a chordal graph with no k + 2-cliques.
The conditions in this conjecture are certainly necessary. A k-inductively pierced code
has an ordering of 0, 1, 2,... k piercings; a quick investigation finds that when removing a
k-piercing, the graph G(C) changes in a very predictable way. In particular, we remove
a vertex v of degree k whose neighborhood, along with v, forms a k + 1-clique. The
inductive ordering of the piercings thus exhibits a perfect elimination ordering [33] for
the graph G(C) which implies that G(C) must be chordal, and by the degree of each

NEURAL IDEALS AND STIMULUS SPACE VISUALIZATION

17

removed vertex we know the graph will be k + 1-colorable and hence contain no k + 2clique. We believe that a similar proof technique to that used in Theorem 3.8 might
be able to extend more generally to prove this conjecture; however, since not even all
2-inductively pierced codes are realizable, it might be more productive to characterize the
graphs of inductively pierced codes rather than the more general classes of k-inductively
pierced codes. Likewise, while the results of Stapleton, et al., [28] imply that any code
which is 1-inductively pierced can be realized with circular place fields, they also show
that 2-inductively pierced codes require additional conditions for realizability that are
not satisfied by every 2-inductively pierced code. It is not yet known if these additional
conditions can be translated into clear conditions on the canonical form.
4. Toric Ideals of k-inductively Pierced Neural Codes
In this section, we discuss necessary and sufficient conditions for 0 and 1-inductively
pierced codes in terms of their corresponding toric ideals. This gives a second computational algebraic geometry approach to checking whether codes are k-inductively pierced.
We begin by investigating 0-inductively pierced codes.
Theorem
4.1. Let C be a code on n neurons such that each neuron fires at least once,
S
i.e. z∈C supp(z) = [n]. Let C be well-formed. Then, the toric ideal IC = h0i if and only
if C is 0-inductively pierced.
In order to prove Theorem 4.1, we will need the following lemma that notes that
crossings of curves in well-formed diagrams result in non-zero toric ideals. The proof is
constructive, describing a quadratic binomial that appears in the toric ideal of a given
neural code if a realization contains a crossing of curves.
Lemma 4.2. Let C ⊂ {0, 1}n be a neural code with abstract diagram DC . If a well-formed
diagram d of DC contains two curves that intersect, then the toric ideal IC is nonempty.
Proof. Let d be a well-formed diagram of DC such that two curves λ1 and λ2 intersect.
Let q be an intersection point of λ1 and λ2 . Since d is well-formed, there exists an open
ball around q, that is contained entirely in a single zone Z of d − λ1 − λ2 with associated
codeword z as illustrated in Figure 3. Thus, the following codewords must be in C:
10z, 01z, 00z, 11z. Then the matrix of the codewords in C looks like


0 1 0 1 ...
 0 0 1 1 ... ,
.
zT zT zT zT . .
and we have
φC (p00z ) =

Y

xi

φC (p10z ) = x1

i∈supp(z)

φC (p01z ) = x2

Y
i∈supp(z)

Y

xi

i∈supp(z)

xi

φC (p11z ) = x1 x2

Y
i∈supp(z)

xi .

18

ELIZABETH GROSS, NIDA KAZI OBATAKE, AND NORA YOUNGS

Therefore p11z p00z − p10z p01z is an element of the toric ideal IC . Indeed,

 
Y
Y
Y
φC (p11z p00z −p10z p01z ) = 
xi · x 1 x2
xi −x1
xi · x 2
i∈supp(z)

i∈supp(z)

i∈supp(z)


Y

xi  = 0.

i∈supp(z)


While our goal is to understand the realization of a code by understanding its toric
ideal, we note that Lemma 4.2 and its proof allow one to understand some things quickly
about a toric ideal of a code simply by noticing motifs, i.e. place field configurations in
its realization. Indeed, we can conclude that there is a quadratic binomial for every two
fields that intersect transversally as in Figure 7. For example, the toric ideal of the code
associated to a chain of n fields as illustrated in Figure 8 contains a quadratic binomials
for each of its n − 1 pairwise intersections.

Figure 7. Two fields that intersect transversally lead to a quadratic binomial in the toric ideal.
Now we proceed to the proof of Theorem 4.1, which states that the toric ideal of a code
is trivial exactly when we fail to see the motif of Figure 7.
Proof of Theorem 4.1. Let C be a well-formed code on n neurons such that each neuron
fires at least once.
(⇒) We will proceed by contradiction. Assume that IC = h0i and that DC is not
inductively 0-pierced. By Proposition 2.7, since DC is not inductively 0-pierced, there is
some well-formed realization of DC with two intersecting curves. Thus, by Lemma 4.2,
the ideal IC is non-empty, a contradiction.
(⇐) Assume that C is 0-inductively pierced. To prove that IC = h0i, we will proceed
by induction on the number of neurons n. If n = 1, then immediately IC = h0i. For
the induction step, assume that IC = h0i for n = r. Now, let n = r + 1. Since C is 0inductively pierced, C has a 0-piercing, λ, such that C − λ is 0-inductively pierced. Thus,
by our induction hypothesis, IC−λ = h0i.

…

Figure 8. A chain of n fields intersecting transversally.

NEURAL IDEALS AND STIMULUS SPACE VISUALIZATION

19

Recall from Section 2.3 that we can understand the toric ideal of a code C, by understanding its hypergraph. So now let us compare the hypergraphs HC−λ and HC . The
hypergraph HC is obtained from HC−λ by adding the vertex i and a single edge containing
i (only a single edge is added by Lemma 3.2). Since there is only one edge that contains
vertex λ, any primitive balanced edge set must be only on the nodes [n] \ λ, and hence
corresponding to a primitive binomial in IC−λ . Therefore, since IC−λ = h0i, the ideal
IC = h0i.

Obtaining results for 1-inductively pierced codes is less direct, and we rely on the
machinery in [15] to give us a combinatorial perspective on the binomials in the toric
ideals. Theorem 4.5 states that the toric ideals of 1-inductively pierced codes are generated
by quadratics. Thus, these codes give an infinite family of toric ideals generated by
quadratics, which we do not believe have been studied before as class of ideals.
We introduce several lemmas before stating and proving Theorem 4.5. We then end
the section with a computational result. For a subset W ⊆ [n], let UW := ∩i∈W Ui .
Lemma 4.3. Let C ⊆ {0, 1}n be well-formed and 1-inductively pierced with associated
hypergraph HC = ([n], E(HC )). Let W ∪ {λ} ∈ E(HC ) with λ ∈
/ W and W 6= ∅. If
UW \ ∪i∈W
U
⊂
U
,
then
there
exists
λ
∈
w
such
that
U
⊂
U
λ
0
λ0
λ , or, in other words,
/ ∪{λ} i
there exists λ0 ∈ W such that for all c ∈ C, if λ0 ∈ supp c then λ ∈ supp c.
Proof. We will proceed by induction on n. For the base case, let n = 2 and W ∪ {λ} ∈
E(HC ). Then W contains exactly one label, and the statement follows immediately.
Now assume the statement holds when n ≤ r. Let n = r + 1. Let W ∪ {λ} ∈ E(HC )
with λ ∈
/ W and W 6= ∅, and assume UW \ ∪i∈W
/ ∪{λ} Ui ⊂ Uλ . Since C is inductively
pierced, there exists a 0 or 1 piercing λ1 in DC such that C − λ1 is 1-inductively pierced.
We now investigate four possible cases based on the relationship of λ1 to λ and W .
(Case 1: λ1 ∈
/ W and λ1 6= λ) Notice that in this case, since λ1 is a 0 or 1-piercing
and can only intersect one other curve, we have UW \ ∪i∈W
/ ∪{λ}∪{λ1 } Ui ⊂ Uλ for any wellformed diagram. Indeed, if UW \ ∪i∈W
/ ∪{λ}∪{λ1 } Ui is not a subset of Uλ , then λ1 intersects
the boundary of UW at point q outside of Uλ such that, within an  ball of q, there exists
a point in UW \ ∪i∈W
/ ∪{λ} Ui that is also outside of Uλ . Thus, the induction hypothesis is
met for C − λ1 , and the statement follows.
(Case 2: λ1 = λ) Notice that a 1-piercing or 0 piercing cannot fully contain another
curve. Thus, since W 6= ∅, and none of the curves whose labels are in W can be fully
contained in Uλ , the curve λ1 = λ must be a 1-piercing, and furthermore, all curves whose
labels are in W must intersect λ1 = λ. However, since λ1 = λ is a 1-piercing there can
only be one curve label λ2 in W . Now, since UW \ ∪i∈W
/ ∪{λ} Ui ⊂ Uλ , the set Uλ2 \ Uλ1 =λ
must be covered by other fields in any well-formed realization of C, however, by wellformedness, this would imply that λ1 = λ intersects at least one more curve in addition
to λ2 , a contradiction.
(Case 3: λ1 ∈ W and λ1 intersects λ) In this case, since λ1 cannot intersect any
additional curves other than λ, we have W = {λ1 }, a contradiction with reasoning parallel
to Case 2.
(Case 4: λ1 ∈ W and λ1 does not intersect λ) Since λ1 does not intersect λ, either
Uλ ⊂ Uλ1 or Uλ1 ⊂ Uλ . However, the fact that λ1 is a 0 or 1-piercing in DC precludes the
former, therefore Uλ1 ⊂ Uλ .

20

ELIZABETH GROSS, NIDA KAZI OBATAKE, AND NORA YOUNGS


Lemma 4.4. Let C ⊆ {0, 1}n be well-formed and 1-inductively pierced. Let HC be the
hypergraph corresponding to C, and let E = (B, R) be a primitive balanced edge set of HC .
Let Z ⊂ [n] and λ ∈ [n] \ Z. If Z ∈ B and {λ} ∪ Z ∈ R, then there exists a hyperedge
{λ} ∪ W ∈ B such that UW \ ∪i∈W
/ ∪{λ} Ui * Uλ in all realizations of C.
Proof. Assume the hypotheses, and, proceeding by contradiction, assume for every hyperedge of the form {λ} ∪ W ∈ B the relationship UW \ ∪i∈W
/ ∪{λ} Ui ⊆ Uλ holds in every
realization of C, or equivalently, UW \ ∪i∈W
U
⊂
U
holds
in every well-formed reλ
/ ∪{λ} i
alization of C. Let B1 , . . . Bt be the hyperedges in B that contain {λ}; note that since
degR λ ≥ 1 and E is balanced, B contains at least one edge containing λ.
By Lemma 4.3, each hyperedge Bi for 1 ≤ i ≤ t contains a vertex that does does not
appear in any edge of HC without λ. Let us denote these vertices uniquely as µ1 , . . . , µs .
Since Z is a hyperedge of HC and does not contain λ, it must be the case µi ∈
/ Z for
1 ≤ i ≤ s. So combining this with the fact that degB µi = degR µi , we have the following
degree counts:
s
X
degB λ =
degB µi , and
i=1

degR λ ≥

s
X

degR µi + 1 =

i=1

However, this contradicts degB λ = degR λ.

s
X

degB µi + 1 = degB λ + 1.

i=1



Theorem 4.5. Let C be well-formed. If C is 1-inductively pierced then the toric ideal IC
is generated by quadratics or IC = h0i.
Proof. Let C be well-formed and assume that C is 1-inductively pierced. Since Theorem 4.1
holds, we can assume without loss of generality that C is not 0-inductively pierced. We will
now proceed by induction on the number of neurons n. The statement holds for n = 2, in
this case, there is a single code C2 = {00, 10, 01, 11} that is 1-inductively pierced, but not
0-inductively pierced; the toric ideal of C2 is generated by a single quadratic, p11 − p10 p01 .
For the induction step assume that IC is generated by quadratics for n = r and let
n = r + 1. Let λ be a 0 or 1-piercing in DC . If λ is a 0-piercing then the statement follows
by the same argument as in the proof of Theroem 4.1, so assume that λ is a 1-piercing.
In particular, assume that λ is a 1-piercing of λ1 in DC identified by zone Z. Let fE be
a primitive binomial in IC of degree at least three and let E = (B, R) be the primitive
balanced edge set of HC that corresponds to fE . Without loss of generality, assume that
|B| ≥ |R|. Note that this means |B| ≥ 3.
If no edge in E contains the vertex λ then E is a balanced edge set on HC−λ and, by
the induction hypothesis, fE is generated by quadratics. Thus, assume there are edges
B1 ∈ B and R1 ∈ R that contain λ, furthermore since E is primitive, B1 6= R1 and thus
without loss of generality we can assume B1 = {λ} ∪ Z and R1 = {λ, λ1 } ∪ Z, the only
two hyperedges in HC that contain λ. We will now proceed to find a proper splitting set
of E.
By Lemma 4.4, there exists a hyperedge B2 = {λ1 } ∪ W ∈ B such that UW \
∪i∈W
/ ∪{λ1 } Ui * Uλ1 in all well-formed realizations of C. Furthermore, by primitivity, R2 6=

NEURAL IDEALS AND STIMULUS SPACE VISUALIZATION

21

B1 and thus λ ∈
/ W . Let d be a well-formed realization of DC . Since UW \ ∪i∈W
/ ∪{λ1 } Ui *
Uλ1 but the intersection of UW \ ∪i∈W
/ ∪{λ1 } Ui and Uλ1 is non-empty, some segment s of
the curve λ1 is contained in UW \ ∪i∈W
/ ∪{λ1 } Ui . Furthermore, since d is well-formed there
is an -neighborhood of s that is fully contained in UW \ ∪i∈w∪{λ
/
/ Ui
1 } Ui . Thus, UW \ ∪i∈W
is non-empty, implying W is an edge in HC .
Now let Γ1 and Γ2 be balanced edge sets such that Γ1blue = {B1 , B2 }, Γ1red = {R1 , W },
Γ2blue = B \ {B1 , B2 } ∪ {W }, and Γ2red = R \ {R1 }. Then S = {W } is a proper splitting
set of E with decomposition (Γ1 , S, Γ2 ) and the proposition follows from Theorem 2.18.

One might expect that the converse of Theorem 4.5 to be true, however there exists a
counterexample with as few as 3 neurons.
Example 4.6. The code C=A1={0, 1}3 is 2-inductively pierced but not 1-inductively
pierced. Notice that in Example 2.9, the cubic p111 − p100 p010 p001 was given as a generator
of IC . However, this cubic can be written in terms of quadratics. In particular,
p111 − p100 p010 p001 = (p111 − p110 p001 ) + p001 (p110 − p100 p010 ).
Thus, we can give a generating set of the toric ideal of A1 that is generated only by
quadratics:
IA1 = hp110 − p100 p010 , p101 − p100 p001 , p011 − p010 p001 , p111 − p110 p001 i.
While the preceding example shows that the converse of Theorem 4.5 is false, we do
note that two-piercings result in signature cubic binomials in the toric ideal.
Proposition 4.7. Let C be a well-formed neural code on n neurons. If there is a triple
intersection in a well-formed realization of C then the toric ideal IC contains a cubic
binomial, in particular, a binomial of the form p111w p2000v − p100v p010v p001w or p111w −
p1000···0 p0100···0 p001w where v, w ∈ {0, 1}n−3 .
Proof. Let C be a well-formed neural code on n neurons with a triple intersection and let
d be a well-formed realization of C. Let us denote the three intersecting curves as λ1 , λ2 ,
and λ3 . Since C is well-formed, all curves intersect generally, so in particular λ1 and λ2
intersect at two points, say p and q. We zoom in on the triple intersection, and we have
a place field arrangement of C as illustrated in Figure 9a.
Since C is well-formed, there exists an open ball around p, so the codewords 000v, 100v,
010v, 110v must be in C for some v ∈ {0, 1}n−3 (see Figure 9b). Similarly, there exists an
open ball around q, so the codewords 111w, 101w, 011w, 001w must be in C , for some
w ∈ {0, 1}n−3 (see Figure 9c).
Then the matrix of the codewords in C looks like


0 1 0 1
1
1
0
0 ...
 0 0 1 1
1
0
1
0 ... 


1
1
1
1 ... ,
 0 0 0 0
.
v T v T v T v T wT wT wT wT . .
and, if v is not the all zeros codeword, we have

22

ELIZABETH GROSS, NIDA KAZI OBATAKE, AND NORA YOUNGS

λ1

p

q

λ2

λ3
(a) A closeup on a triple intersection.

λ1
000v

λ1

λ2
111w

100v

010v

p

101w

110v
λ3
(b) A closeup on the point of intersection p.

011w

λ2

q
001w

(c) A closeup on the point of intersection q

Figure 9. Closeups on the points of intersection in a triple intersection of
curves.

φC (p000v ) =

Y

xi

φC (p100v ) = x1

i∈supp(v)

φC (p010v ) = x2

xi

i∈supp(v)

Y

xi

φC (p001w ) = x3

i∈supp(v)

φC (p111w ) = x1 x2 x3

Y

Y

Y

xi

i∈supp(w)

xi .

i∈supp(w)

Therefore, p111w p2000v − p100v p010v p001w is in the toric ideal IC . If v is the all zeros
codeword then p111w − p1000···0 p0100···0 p001w ∈ IC .


NEURAL IDEALS AND STIMULUS SPACE VISUALIZATION

23

In essence, Proposition 4.7 tells us that if we notice three fields intersecting as in Figure
4a, then we can expect a particular cubic in the toric ideal. While Example 4.6 shows
that it is possible for this cubic to be generated by quadratics in the ideal, we wonder
whether there exist term orders such that these signature cubics appear in the reduced
Gröbner basis. Using the Macaulay2 interface for gfan [19], we are able to find a term
order that works in this sense for n = 3.
In the following proposition, we use a weighted graded reverse lexicographic monomial
order: Let K[x1 , . . . , xn ] be a polynomial ring, and let w ∈ Rn be a weight vector. Let
degw (xa ) = a1 w1 + a2 w2 + . . . + an wn and let xa < xb if and only if degw (xa ) < degw (xb )
or degw (xa ) = degw (xb ) and there exists 1 ≤ i ≤ n such that an = bn , . . . , ai+1 = bi+1 ,
ai > bi [36]. Furthermore, to make the statement of Proposition 4.8 cleaner, we will view
each IC as a subset of the larger polynomial ring K[p100 , p010 , p001 , p110 , p101 , p011 , p111 ].
Proposition 4.8. A well-formed neural code C on 3 neurons is 1-inductively pierced if
and only if the Gröbner basis of IC with respect to the weighted graded reverse lexicographic
order with the weight vector w = (0, 0, 0, 1, 1, 1, 0) contains only binomials of degree 2 or
less.
Proof. Using the weighted graded reverse lexicographic order with weight vector w =
(0, 0, 0, 1, 1, 1, 0) we computed the reduced Gröbner bases of the toric ideals of each wellformed neural code up to symmetry. We found that only the 0- and 1- inductively pierced
codes had reduced Gröbner bases with maximum degree two.

We end this section with the following conjecture.
Conjecture 4.9. For each n, there exists a term order such that a code is 0- or 1inductively pierced if and only if the reduced Gröbner basis contains binomials of degree 2
or less.
5. Conclusion: Drawing place fields for neural codes
Our motivating question is how to draw the realization of a place field diagram for a
neural code assuming we know a priori that it is convexly realizable in dimension two.
Existing work in the field of information theory [28] gives an algorithm for drawing such
realizations when the data sets, i.e. codes, are inductively pierced. Thus, our question
of focus for this manuscript is how to determine whether a neural code is inductively
pierced, or k-inductively pierced. To this end, we utilized two different algebraic objects,
the neural ideal and the toric ideal of a neural code. The following theorem summarizes
our results.
Theorem 5.1. (Summary of results) Let C be a well-formed neural code on n neurons.
(1) The neural code C is 0-inductively pierced if and only if CF (JC ) = {fij | i, j ∈
[n], i < j, fij ∈ {xi xj , xi (1 − xj ), xj (1 − xi )}.
(2) C is 1-inductively pierced if and only if CF (JC ) consists only of degree two pseudomonomials meeting the following conditions:
(i) For each pair {i, j}, at most one of xi xj , xi (1 − xj ), xj (1 − xi ) appears in
CF (JC ).
(ii) G(C) is a forest.

24

ELIZABETH GROSS, NIDA KAZI OBATAKE, AND NORA YOUNGS

(3) The neural code C is 0-inductively pierced if and only if IC = h0i.
(4) If the neural code C is 0 and 1-inductively pierced then IC is h0i or generated by
quadratics.
Using the canonical form of the neural ideal, we have fully classified 0- and 1-inductively
pierced codes. For toric ideals, we have a full understanding of 0-inductively pierced
codes and a partial understanding of 1-inductively pierced codes. However, in the big
picture, this work is still in progress. One goal for further work is to completely classify
k-inductively pierced codes using their toric ideals; another is classify them using their
canonical forms.
We end here with a large example, illustrating our results. Consider the following neural
code on 17 neurons:
C = {c0 = 00000000000000000, c1 = 10000000000000000, c2 = 11000000000000000,
c3 = 11100000000000000, c4 = 10100000000000000, c5 = 10010000000000000,
c6 = 10011000000000000, c7 = 00010000000000000, c8 = 00011000000000000,
c9 = 00011100000000000, c10 = 00010100000000000, c11 = 00010010000000000,
c12 = 00010001000000000, c13 = 00010001100000000, c14 = 00000001100000000,
c15 = 00000001110000000, c16 = 00000001010000000, c17 = 00000001011000000,
c18 = 00000001001000000, c19 = 00000001000000000, c20 = 00000001000100000,
c21 = 00000001000110000, c22 = 00000001000010000, c23 = 00000001000011000,
c24 = 00000000000010000, c25 = 00000000000011000, c26 = 00000000000010100,
c27 = 00000000000010010, c28 = 00000000000010001}.
We compute the canonical form of the neural ideal CF (JC ), determine the graph of the
code G(C), and compute its toric ideal IC . The toric ideal of C is
IC = hpc20 pc24 − pc21 , pc19 pc24 − pc22 , pc19 pc25 − pc23 , pc16 pc18 − pc23 , pc16 pc18 − pc17 pc19 ,
pc14 pc16 − pc15 pc19 , pc7 pc9 − pc8 pc10 , pc7 pc19 − pc12 , pc7 pc14 − pc13 , pc1 pc3 − pc2 pc4 ,
pc1 pc7 − pc5 , pc1 pc8 − pc6 i.
From these computations we see that IC is generated by binomials of degree at most
2. Thus, from our results we know that C is not 0-inductively pierced and is possibly
1-inductively pierced. The canonical form will give us more information.
The pseudo-monomials in the canonical form and the graph G(C) are listed in Appendix
B. Since for each pair {i, j}, at most one of xi xj , xi (1 − xj ), and xj (1 − xi ) appears in
CF (JC ) and since G(C) is a forest, by Theorem 3.8, the code C is 1-inductively pierced.
Thus, we can use the existing algorithm in [28] that draws Euler diagrams with circles. The algorithm is implemented and available at http://www.eulerdiagrams.org/
inductivecircles.html. Figure 10 shows the input and output of the program. Note
that to input the code in this program we rename each codeword to its support, where
a=1, b=2, etc., omitting commas and braces. The output of the program is a place field
diagram of C.

NEURAL IDEALS AND STIMULUS SPACE VISUALIZATION

25

Finally, from Algorithm 3.10 in Section 3, we determine a drawing order for this place
field diagram of C as follows:
(ix) 11 (1-piercing of 10 in 8),
(i) 1 (0-piercing in ∅),
(x) 12 (1-piercing of 13 in 8),
(ii) 4 (1-piercing of 1),
(xi) 14 (1-piercing of 8 in 13),
(iii) 8 (1-piercing of 4),
(xii) 2 (0-piercing in 1),
(iv) 13 (1-piercing of 8),
(xiii) 3 (1-piercing of 2 in 1),
(v) 5 (1-piercing of 1 in 4),
(xiv) 7 (0-piercing in 4),
(vi) 6 (1-piercing of 5 in 4),
(xv) 15 (0-piercing in 13),
(vii) 9 (1-piercing of 4 in 8),
(xvi) 16 (0-piercing in 13),
(viii) 10 (1-piercing of 9 in 8),
(xvii) 17 (0-piercing in 13).

Figure 10. A place field diagram of a 17-neuron code drawn using the
implemented algorithm from [28].
6. Acknowledgements
This collaboration is a result of the 2014 AMS Mathematics Research Community, “Algebraic and Geometric Methods in Applied Discrete Mathematics,” which was supported
by NSF DMS-1321794. Elizabeth Gross was supported by NSF DMS-1304167. The authors would like to thank Tim Hsu and Richard Kulbeka for their extensive comments on
a preliminary version of this work.

26

ELIZABETH GROSS, NIDA KAZI OBATAKE, AND NORA YOUNGS

Appendix A.
Generators for the n = 3 case
Below is a table of the generating sets of IA , the toric ideal, for the different codes on
n = 3 neurons listed in Figure 6 of the original paper on the neural ring [?].
Generators of IA
p111 − p100 p010 p001
p110 − p100 p010
p101 − p100 p001
p011 − p010 p001
p111 − p010 p101
p110 − p100 p010
p111 − p100 p010 p001
p110 − p100 p010
p101 − p100 p001
p111 − p100 p011
p110 − p100 p010
p100 p011 − p010 p101
p110 − p100 p010
p100 p111 − p110 p101
p111 − p010 p101
p111 − p100 p010 p001
p110 − p100 p010
p111 − p100 p011
p111 − p010 p101
p100 p011 − p010 p101
p2100 p011 − p110 p101
p111 − p100 p011
p111 − p100 p010 p001
p2111 − p110 p101 p011
p101 − p100 p001
p110 − p100 p010
p100 p011 − p010 p101
p011 − p010 p001
p101 − p100 p001
p110 − p100 p001
p110 − p100 p010
p100 p011 − p010 p101
p2100 p011 − p110 p101
0

Codes
A1

A2
A3

A4

A5, B2, C1, F 1
A6
A7
A8
A9, A16
A10
A11
A14
A15
B1
B3
E1

E2

E3
A12, A13, A17, A18, A19, A20, B4, B5, B6, C2, C3, D1, E4, F 2, F 3, G1, H1, I1

NEURAL IDEALS AND STIMULUS SPACE VISUALIZATION

x2 (1 − x1 )
x3 (1 − x1 )
x5 (1 − x4 )
x6 (1 − x4 )
x7 (1 − x4 )
x9 (1 − x8 )
x10 (1 − x8 )
x11 (1 − x8 )
x12 (1 − x8 )
x14 (1 − x13 )
x15 (1 − x13 )
x16 (1 − x13 )
x17 (1 − x13 )
x1 x6
x1 x7
x1 x8
x1 x9
x1 x10
x1 x11
t x1 x12
x1 x13
x1 x14
x1 x15
x1 x16
x1 x17
Table 2. Canonical form of
Section 5.

27

x2 x4 x3 x15 x6 x10 x9 x15
x2 x5 x3 x16 x6 x11 x9 x1 6
x2 x6 x3 x17 x6 x12 x9 x17
x2 x7 x4 x10 x6 x13 x10 x12
x2 x8 x4 x11 x6 x14 x10 x13
x2 x9 x4 x12 x6 x15 x10 x14
x2 x10 x4 x13 x6 x16 x10 x15
x2 x11 x4 x14 x6 x17 x10 x16
x2 x12 x4 x15 x7 x8 x10 x17
x2 x13 x4 x16 x7 x9 x11 x12
x2 x14 x4 x17 x7 x10 x11 x13
x2 x15 x5 x7 x7 x11 x11 x14
x2 x16 x5 x8 x7 x12 x11 x15
x2 x17 x5 x9 x7 x13 x11 x16
x3 x4 x5 x10 x7 x14 x11 x17
x3 x5 x5 x11 x7 x15 x12 x14
x3 x6 x5 x12 x7 x16 x12 x15
x3 x7 x5 x13 x7 x17 x12 x16
x3 x8 x5 x14 x8 x15 x12 x17
x3 x9 x5 x15 x8 x16 x14 x15
x3 x10 x5 x16 x8 x17 x14 x16
x3 x11 x5 x17 x9 x11 x14 x17
x3 x12 x6 x7 x9 x12 x15 x16
x3 x13 x6 x8 x9 x13 x15 x17
x3 x14 x6 x9 x9 x14 x16 x17
the neural ideal for the 17-neuron code from

Appendix B.
Computation for a 17-neuron code
The generators of the toric ideal of the 17-neuron code from Section 5:
IC = hpc20 pc24 −pc21 , pc19 pc24 −pc22 , pc19 pc25 −pc23 , pc16 pc18 −pc23 , pc16 pc18 −pc17 pc19 , pc14 pc16 −
pc15 pc19 , pc7 pc9 −pc8 pc10 , pc7 pc19 −pc12 , pc7 pc14 −pc13 , pc1 pc3 −pc2 pc4 , pc1 pc7 −pc5 , pc1 pc8 −pc6 i.

28

ELIZABETH GROSS, NIDA KAZI OBATAKE, AND NORA YOUNGS

13
12

8

4

14

16

7

17

15

1

9

5

10

6

11
3

2

Figure 11. The graph G(C) of the 17-neuron code.
References
[1] M. A. Atherton, R. A. Bates, H. P. Wynn. Dimensional Analysis Using Toric Ideals: Primitive
Invariants. PLoS ONE, 9 (2014) no. 12: e112827.
[2] S. Chow. Generating and drawing area-proportional Euler and Venn diagrams. Ph.D. dissertation,
University of Victoria (2007).
[3] G. Craciun, A. Dickenstein, A. Shiu, and B. Sturmfels. Toric dynamical systems, J. Symbolic Comput., 44 (2009) no. 11, 1551–1565.
[4] G. Craciun, L. D. Garcia-Puente, and F. Sottile. Some geometrical aspects of control points for toric
patches. Mathematical methods for curves and surfaces. Springer Berlin Heidelberg, (2008), 111–135.
[5] C. Curto, E. Gross, J. Jeffries, K. Morrison, M. Omar, Z. Rosen, A. Shiu, N. Youngs. What makes
a neural code convex? arXiv:1508.00150 (2015).
[6] C. Curto and V. Itskov. Cell groups reveal structure of stimulus space. PLoS Comput. Biol., 4 (2008)
no. 10:e1000205.
[7] C. Curto, V. Itskov, K. Morrison, Z. Roth, and J. L. Walker. Combinatorial neural codes from a
mathematical coding theory perspective. Neural Comput., 25 (2013) no. 7, 1891–1925.
[8] C. Curto, V. Itskov, A. Veliz-Cuba, and N. Youngs. The neural ring: an algebraic tool for analyzing
the intrinsic structure of neural codes. Bull. Math. Biol., 75 (2013) no. 9, 1571–1611.
[9] C. Curto and N. Youngs. Neural ring homomorphisms and maps between neural codes.
arXiv:1511.00255, (2015).
[10] P. Diaconis and B. Sturmfels. Algebraic algorithms for sampling from conditional distributions. Ann.
Statist. 26 (1998) no. 1, 363–397.
[11] M. Drton, B. Sturmfels and S. Sullivant. Lectures on algebraic statistics, Oberwolfach Seminars 39,
Birkhäuser (2009).
[12] J. Flower and J. Howse. Generating Euler diagrams. Proceedings of 2nd International Conference on
the Theory and Application of Diagrams, Springer (2002) 61–75.
[13] C. Giusti and V. Itskov. A no-go theorem for one-layer feedforward networks. Neural Comput., 26
(2014) no. 11, 2527–2540.
[14] C. Giusti, V. Itskov, and W. Kronholm. On convex codes and intersection violators. In preparation.
[15] E. Gross and S. Petrović. Combinatorial degree bound for toric ideals of hypergraphs. International
Journal of Algebra and Computation, 23 (2013) no. 6, 1503–1520.
[16] D. R. Grayson and M. Stillman. Macaulay2, a software system for research in algebraic geometry.
Available at http://www.math.uiuc.edu/Macaulay2/.
[17] Sir W. Hamilton. Lectures on Metaphysics and Logic, edited by Henry Longueville, Mansel and John
Veitch. William Blackwood and Sons, Edinburgh and London, 1860.

NEURAL IDEALS AND STIMULUS SPACE VISUALIZATION

29

[18] D. H. Hubel and T. N. Wiesel. Place fields of single neurons in the cat’s striate cortex. J. Physiol.,
148 (1959) no. 3, 574–591.
[19] A. N. Jensen. Gfan, a software system for Gröbner fans and tropical varieties. Available at http:
//home.imf.au.dk/jensen/software/gfan/gfan.html/.
[20] C. Lienkaemper, A. Shiu, and Z. Woodstock. Obstructions to convexity in neural codes.
arXiv:1509.03328, (2015).
[21] E. Miller and B. Sturmfels. Combinatorial commutative algebra. Graduate Texts in Mathematics,
227, Springer-Verlag, New York, (2005).
[22] J. O’Keefe and J. Dostrovsky. The hippocampus as a spatial map. Preliminary evidence from unit
activity in the freely-moving rat. Brain Res., 34 (1971) no. 1, 171–175.
[23] L. Pachter and B. Sturmfels (eds), Algebraic Statistics for Computational Biology, Cambridge University Press, New York, 2005.
[24] S. Petrović, A. Rinaldo and S. Fienberg. Algebraic statistics for a directed random graph model with
reciprocation, Algebraic Methods in Statistics and Probability II, M. Viana and H. Wynn (editors).
CONM, vol 516. AMS.
[25] S. Petrović and D. Stasi. Toric algebra of hypergraphs. Journal of Algebraic Combinatorics, 39
(2014) no. 1, 187–208.
[26] P. Rodgers, L. Zhang, and A. Fish. General Euler diagram generation. International Conference on
the Theory and Application of Diagrams, Springer (2008).
[27] P. Simonetto, D. Auber, and D. Archambault. Fully automatic visualisation of overlapping sets.
Computer Graphics Forum, 28 (2009) no. 3.
[28] G. Stapleton, L. Zhang, J. Howse, and P. Rodgers. Drawing Euler Diagrams with Circles: The
Theory of Piercings. Visualization and Computer Graphics, IEEE Transactions, 17 (2011) no. 7,
1020–1032.
[29] William A. Stein et al. Sage Mathematics Software (Version 7.2), The Sage Development Team,
(2016), available at http://www.sagemath.org.
[30] B. Sturmfels, Gröbner bases and convex polytopes, University Lecture Series, 8. American Mathematical Society, 1996.
[31] B. Sturmfels and S. Sullivant. Toric ideals of phylogenetic invariants. Journal of Computational
Biology, 12 (2005) no. 2, 204–228.
[32] R. Villarreal. Monomial Algebras. Monographs and Textbooks in Pure and Applied Mathematics,
238, Marcel Dekker, Inc., New York, 2001.
[33] D. West. Introduction to Graph Theory (2nd ed.) Prentice Hall, Upper Saddle River, NJ, 2001.
[34] E. Gross and S. Petrović. Combinatorial degree bound for toric ideals of hypergraphs.
arXiv:1206.2512, (2012).
[35] 4ti2 team. 4ti2—A software package for algebraic, geometric and combinatorial problems on linear
spaces. Available at www.4ti2.de/.
[36] SageMath. The Sage Developers. SageMath, the Sage Mathematics Software System (Version 7.1).
Available at http://www.sagemath.org.
E-mail address: elizabeth.gross@sjsu.edu
E-mail address: nida.kazi@sjsu.edu
E-mail address: nyoungs@hmc.edu
Department of Mathematics and Statistics, One Washington Square, San José State
University, San José, CA, 95192-0103, USA
Department of Mathematics, Harvey Mudd College, 301 Platt Boulevard, Claremont,
CA, 91711-5901

