# Partial Dyck paths with Air Pockets

Helmut Prodinger  Helmut Prodinger, Mathematics Department, Stellenbosch
University, 7602 Stellenbosch, South Africa, and NITheCS (National Institute
for Theoretical and Computational Sciences), South Africa<EMAIL_ADDRESS>
###### Abstract.

Dyck paths with air pockets are obtained from ordinary Dyck paths by
compressing maximal runs of down-steps into giant down-steps of arbitrary
size. Using the kernel method, we consider partial Dyck paths with air
pockets, both, from left to right and from right to left.

In a last section, the concept is combined with the concept of skew Dyck
paths.

##  1\. Introduction

In a paper that was posted on valentine’s day [1], Baril et al. introduced a
new family of Dyck-like paths, called _Dyck paths with air pockets_. Many of
the usual parameters that one could think of are investigated in this paper.
The paths have the usual up-steps $(1,1)$ and down-steps $(1,-k)$ for any
$k=1,2,\dots$, but no such down-steps may follow each other. Otherwise, they
cannot go into negative territory, and must end at the $x$-axis, as usual. One
could just think about ordinary Dyck paths, and each (maximal) run of down-
steps is condensed into one (giant) downstep.

The Figure 1 explains the actions readily.

Figure 1. Graphical description of Dyck paths with air pockets. Top layer
describes the situation after an up-step, bottom layer after a down-step.

We introduce generating functions $f_{k}(z)$ and $g_{k}(z)$ where the
coefficient of $z^{n}$ in one of these functions counts paths ending in the
respective state according to the number of steps. The function
$f_{0}(z)+g_{0}(z)$ counts the Dyck paths with air pockets, as the zero in the
index just means that they returned to the $x$-axis.

In this short paper, we will enumerate _partial_ Dyck paths with air pockets,
namely we allow the path to end at level $i$. In other words, we compute all
$f_{k}(z)$ and $g_{k}(z)$.

Our instrument of choice is the kernel method, as can be found in the popular
account [2].

##  2\. Generating functions

Just looking at Figure 1, we find the following recursion, where we write
$f_{k}$ for $f_{k}(z)$ for simplicity:

$\displaystyle f_{0}$ $\displaystyle=1,$ $\displaystyle f_{k}$
$\displaystyle=zf_{k-1}+zg_{k-1},\quad k\geq 1,$ $\displaystyle g_{k}$
$\displaystyle=zf_{k+1}+zf_{k+2}+zf_{k+3}+\cdots,$

and now we introduce bivariate generating functions

$F(u,z)=F(u)=\sum_{k\geq 0}u^{k}f_{k}(z),\quad G(u,z)=G(u)=\sum_{k\geq
0}u^{k}g_{k}(z).$

Summing the recursions,

$F(u)=1+zuF(u)+zuG(u)$

and

$G(u)=\sum_{k\geq
0}u^{k}z\sum_{j>k}f_{j}=z\sum_{j>0}f_{j}\sum_{k=0}^{j-1}u^{k}=z\sum_{j>0}f_{j}\frac{1-u^{k}}{1-u}=\frac{z}{1-u}(F(1)-F(u)).$

Eliminating one function, we are left to analyze

$F(u)=1+zuF(u)+\frac{z^{2}u}{1-u}(F(1)-F(u)).$

Solving, we find

$F(u)=\frac{1-u+{z}^{2}uF(1)}{-zu+z{u}^{2}+{z}^{2}u+1-u}=\frac{1-u+{z}^{2}uF(1)}{z(u-s_{1})(u-s_{2})},$

with

$\displaystyle s_{1}$
$\displaystyle=\frac{1+z-{z}^{2}+\sqrt{-{z}^{2}-2{z}^{3}-2z+{z}^{4}+1}}{2z},$
$\displaystyle s_{2}$
$\displaystyle=\frac{1+z-{z}^{2}-\sqrt{-{z}^{2}-2{z}^{3}-2z+{z}^{4}+1}}{2z}.$

Note that $s_{1}s_{2}=\frac{1}{z}$. We still need to compute $F(1)$. Before we
can plug in $u=1$ and compute it, we must cancel the bad factor of both,
numerator and denominator. In this case, this is the factor $u-s_{2}$, since
the reciprocal of it would not allow a Taylor expansion around $u=1$. The
result is

$F(u)=\frac{-1+z^{2}F(1)}{zs_{2}-z+z^{2}-1+zu},$

from which we now can compute $F(1)$ by plugging in $u=1$. We get

$F(1)=\frac{-1+z^{2}F(1)}{zs_{2}+z^{2}-1}=\frac{1}{1-zs_{2}}$

and therefore

$F(u)=\frac{1-s_{1}}{1-zs_{2}}\frac{1}{u-s_{1}}=-\frac{1}{s_{1}}\frac{1-s_{1}}{1-zs_{2}}\frac{1}{1-u/s_{1}}.$

Reading off the coefficient of $u^{k}$, we further get

$f_{k}=-\frac{1}{s_{1}^{k+1}}\frac{1-s_{1}}{1-zs_{2}}=-z^{k+1}s_{2}^{k+1}\frac{1-1/(zs_{2})}{1-zs_{2}}=-z^{k}s_{2}^{k}\frac{zs_{2}-1}{1-zs_{2}}=z^{k}s_{2}^{k}.$

Since $G(u)=\dfrac{F(u)-1-zuF(u)}{zu}$, we also find

$g_{k}=\frac{1}{z}f_{k+1}-f_{k}=z^{k}(s_{2}^{k+1}-s_{2}^{k}).$

We can also compute $\textsc{total}(z)=F(1,z)+G(1,z)$ which counts path that
end anywhere, and the result is

$\textsc{total}(z)={\frac{1-z-{z}^{2}-\sqrt{-{z}^{2}-2{z}^{3}-2z+{z}^{4}+1}}{2{z}^{3}}}=\frac{1}{z^{2}}g_{0}.$

In retrospective, this is not surprising, since if we consider paths that end
at state 0 in the bottom layer, and we go back the last 2 steps, we could have
been indeed in any state.

It is worthwhile to notice that

$f_{0}+g_{0}=1+z^{2}+z^{3}+2z^{4}+4z^{5}+8z^{6}+17z^{7}+37z^{8}+82z^{9}+185z^{10}+423z^{11}+\cdots$

and the coefficients $1,1,2,4,8,17,\dots$ are sequence A004148 in [4].

######  Theorem 1.

The generating functions describing partial Dyck paths with air pockets,
landing in state $k$ of the upper/lower layer, are given by

$f_{k}=z^{k}s_{2}^{k},\quad g_{k}=z^{k}(s_{2}^{k+1}-s_{2}^{k}).$

In particular, $f_{k}+g_{k}=z^{k}s_{2}^{k+1}$ is the generating function of
partial paths ending at level $k$.

##  3\. Right to left model

Reading Dyck paths with air pockets from right to left means to have arbitrary
long up-steps, but only one at the time. While the enumeration for those paths
that end at the $x$-axis is the same as before, this is not the case for
_partial_ paths.

Figure 2 explains the concept. The generating functions $a_{k}$ refer to the
top layer and $b_{k}$ to the bottom layer.

Figure 2. Graphical description of Dyck paths with air pockets. Top layer
describes the situation after a down-step, bottom layer after an up-step.

The recursions are111Iverson’s notation is used here.

$\displaystyle a_{k}$ $\displaystyle=[k=0]+zb_{k+1},$ $\displaystyle b_{k}$
$\displaystyle=zb_{k+1}+z\sum_{0\leq j<k}a_{j}.$

With bivariate generating functions analogously to before, we find by summing

$A(u)=1+\frac{z}{u}(B(u)-b_{0})$

and

$B(u)=\frac{z}{u}(B(u)-b_{0})+z\sum_{0\leq
j<k}a_{j}u^{k}=\frac{z}{u}(B(u)-b_{0})+\frac{zu}{1-u}A(u).$

One variable can be eliminated:

$B(u)=\frac{z}{u}(B(u)-b_{0})+\frac{zu}{1-u}+\frac{z^{2}}{1-u}(B(u)-b_{0}).$

Solving

$B(u)={\frac{z\left(B(0)-B(0)u-{u}^{2}+zB(0)u\right)}{z-zu+{z}^{2}u-u+{u}^{2}}}$

The denominator factors as $(u-s_{1}^{-1})(u-s_{2}^{-1})$. The bad factor is
this time $(u-s_{1}^{-1})$. Dividing it out,

$B(u)=\frac{z\left(-us_{1}-B(0)s_{1}+B(0)s_{1}z-1\right)}{us_{1}-zs_{1}+{z}^{2}s_{1}-s_{1}+1}$

and further

$B(0)=b_{0}=\frac{z}{s_{1}-1}=s_{2}-1.$

Thus, after some simplifications,

$B(u)=-z+\frac{zs_{1}}{(s_{1}-1)(1-\frac{u}{zs_{1}})},$

or

$B(u)=-z+\frac{1}{s_{2}(s_{1}-1)(1-s_{2}u)}=-z+\frac{s_{2}-1}{zs_{2}(1-s_{2}u)}$

and then

$b_{k}=\frac{s_{2}-1}{z}s_{2}^{k-1},\quad k\geq 1.$

The functions $a_{k}$ could be computed from here as well, but for the partial
paths only the functions $b_{k}$ are of relevance, if we don’t consider the
empty path.

######  Theorem 2.

The generating functions of partial Dyck paths with air pockets in the right
to left model are

$\displaystyle 1+b_{0}=s_{2}$

and

$b_{k}=\frac{s_{2}-1}{z}s_{2}^{k-1},\quad k\geq 1.$

To consider the total does not make sense, since in just 1 or 2 steps, every
state can be reached, so a sum over $b_{k}$ would not converge.

##  4\. Skew Dyck paths with air pockets

The walks according to Figure 3 are related to skew Dyck paths [3]; the red
down-steps are modeled to stand for south-west steps, and the way they are
arranged, there are no overlaps of such a path. See [3] and the references
cited there.

Figure 3. Three layers of states according to the type of steps leading to
them (up, down-black, down-red).

Now we combine this model with air pockets. Each maximal sequence of black
down-steps is condensed into one giant down-step, depicted in dashed grey in
Figure 4

Figure 4. Three layers of states according to the type of steps leading to
them (up, down-black, down-red). Black down-steps are condensed into giant
grey down-steps.

Introducing generating functions, according to the three layers, we find the
following recursions by inspection;

$\displaystyle a_{0}$ $\displaystyle=1,\quad a_{k+1}=za_{k}+zb_{k},\ k\geq 0,$
$\displaystyle b_{k}$ $\displaystyle=z\sum_{j>k}a_{j}+z\sum_{j>k}c_{j},$
$\displaystyle c_{k}$ $\displaystyle=zb_{k+1}+zc_{k+1}.$

Translating these into bivariate generating functions, we further have

$\displaystyle A(u)=1+zuA(u)+zuB(u),$ $\displaystyle
B(u)=\frac{z}{1-u}[A(1)-A(u)]+\frac{z}{1-u}[C(1)-C(u)],$ $\displaystyle
C(u)=zuB(u)+zuC(u).$

Solving,

$\displaystyle A(u)$
$\displaystyle={\frac{{z}^{3}{u}^{2}A(1)+{z}^{3}{u}^{2}C(1)-z{u}^{2}-{z}^{2}uC(1)-{z}^{2}u-{z}^{2}uA(1)+zu+u-1}{\left(-1+zu\right)\left(z{u}^{2}+2{z}^{2}u-zu-u+1\right)}},$
$\displaystyle B(u)$
$\displaystyle=-{\frac{\left(-A(1)-C(1)+zuA(1)+zuC(1)+1\right)z}{z{u}^{2}+2{z}^{2}u-zu-u+1}},$
$\displaystyle C(u)$
$\displaystyle={\frac{{z}^{2}u\left(-A(1)-C(1)+zuA(1)+zuC(1)+1\right)}{\left(-1+zu\right)\left(z{u}^{2}+2{z}^{2}u-zu-u+1\right)}}.$

We factor $z{u}^{2}+2{z}^{2}u-zu-u+1=(u-s_{1})(u-s_{2})$ with

$s_{2}={\frac{-2{z}^{2}+z+1-\sqrt{4{z}^{4}-4{z}^{3}-3{z}^{2}-2z+1}}{2z}},\quad
s_{1}=\frac{1}{zs_{2}}.$

Since $A(u)-C(u)=\frac{1}{1-zu}$, we have $A(1)-C(1)=\frac{1}{1-z}$, and we
only need to compute one of them. Dividing the (bad) factor $(u-s_{2})$ out,
plugging in $u=1$ and solving leads to

$A(1)={\frac{-s_{2}z+2-z}{2\left(1-s_{2}z\right)\left(1-z\right)}}=\frac{1}{2(1-z)}+\frac{1}{2(1-zs_{2})}$

and

$C(1)=-\frac{1}{2(1-z)}+\frac{1}{2(1-zs_{2})}.$

Using these values, we find

$A(u)+B(u)+C(u)=\frac{s_{2}(1-z^{2}-zs_{2})}{(1-zs_{2})(1-uzs_{2})}$

and furthermore

$[u^{k}](A(u)+B(u)+C(u))=\frac{z^{k}s_{2}^{k+1}(1-z^{2}-zs_{2})}{(1-zs_{2})}$

These functions describe all skew Dyck paths with air pockets, ending at level
$k$. For $k=0$, this yields

$1+z^{2}+z^{3}+3z^{4}+7z^{5}+17z^{6}+45z^{7}+119z^{8}+323z^{9}+893z^{10}+2497z^{11}+\cdots.$

## References

  * [1] Jean-Luc Baril, Sergey Kirgizov, Rémi Maréchal, Vincent Vajnovszki, Enumeration of Dyck paths with air pockets, arXiv:2202.06893.
  * [2] H. Prodinger,  The kernel method: A collection of examples,  Sém. Lothar. Combin., B50f (2004), 19 pages.
  * [3] H. Prodinger, Partial skew Dyck paths—a kernel method approach, preprint, 2021.
  * [4] N. J. A. Sloane et al., The On-line Encyclopedia of Integer Sequences, 2022.


# A General Approach to Coding in Early Olfactory and Visual Neural
Populations

###### Abstract

Recent experimental and theoretical work on neural populations belonging to
two separate early sensory systems, olfaction and vision, has challenged the
notion that the two operate under different computational paradigms by
providing evidence for the respective neural population codes having three
central, common features: they are highly redundant; they are organized such
that information is carried in the identity, and not the relative timing, of
the active neurons; they are capable of error correction. We present the first
model that captures these three properties in a general manner, making it
possible to investigate whether similar structure is present in other
population codes. Our model also makes specific predictions about additional,
as yet unseen, structure in such codes. If these predictions are found in real
data, this would provide new evidence that such population codes are operating
under more general computational principles.

## A General Approach to Coding in Early Olfactory and Visual Neural
Populations

William T. Redman

University of California, Santa Barbara

<EMAIL_ADDRESS>
## Introduction

Because of their relative ease to record from and their importance in being
the input to upstream brain areas, the coding properties of neural populations
belonging to early sensory systems have been the focus of a large body of
experimental and theoretical literature. This work has explored the precision
of retinal spike trains [1], the correlation structure of individual retinal
ganglion cells and their population wide collective states [2], [3], the
possibility of criticality in retinal populations [4], [5], the preservation
of odor identity representation by glomeruli (structures in the olfactory bulb
that receive projections from olfactory sensory neurons - OSNs) across varying
odor concentrations [6], [7], [8], [9] and the combinatorial nature of the
glomeruli code [10], [11]. While the respective work has followed a similar
mission (to understand the nature of the population codes), the results have
caused a divergence in the belief of the coding principles at use. Yet, in
both systems, the exact structure of the exact nature of the population code
has been unclear.

Recent work has taken advantage of advances in recording and manipulation
technology, as well as statistical methods, to probe more intricately at this
question of the exact structure of the retinal ganglion and the glomeruli
population codes [12], [13], [14], [15]. Despite the differences in system and
approach, the two have converged on three similar principles for the
respective codes. First, the codes are highly redundant, as only a small
subset of the neurons are responsible for carrying the information about the
identity of any given stimulus (whether it be some feature of the visual field
or an odor). Second, it is the identity of these neurons in the specific
subset (and not their relative timing) that carries the relevant information.
Finally, a neural population code with those two features is endowed with the
capability to be robust to noise, in the sense that the code is capable of
error correction. These core similarities clearly challenge the assumption
that the two systems are operating under different coding paradigms.

In the retinal ganglion population code, these features come about by the fact
that the probability space of population responses is populated by geometric
objects identified as ridges. These ridges correspond to unique “codewords”
that a downstream system maps all responses in the ridge to [13]. The identity
of these ridges is determined by an active set of neurons (those neurons that
were active in the states that make up a given ridge) and a silent set (those
neurons that weren’t active). The mapping from a given neural response to the
appropriate, ridge-specific codeword was hypothesized to be achieved by an
additional layer of neurons, each one firing if a certain fraction of neurons
in a given active set fire and none of neurons in the corresponding silent set
fire (see [13] Fig. 13). Under this simple model, it’s easy to see that there
could be a number of population response states that get mapped to the same
codeword.

In the glomeruli population code, these features arise from the fact that the
code has been found operate under the “Primacy Hypothesis”, namely that it is
the first $n$ active glomeruli that are responsible for encoding odor identity
[14]. Therefore, all population responses that have the same first $n$ active
glomeruli (where the order of the first $n$ active glomeruli doesn’t matter
[14]), are recognized as being the same odor. Any of those given states can
therefore be seen as a codeword. The relevant time scale (which determines the
relevant $n$) was found to be $<100$ ms [14]. Whether $n$ is fixed, or whether
it can vary for various odors and odor mixtures, has yet to be determined.

Recent theoretical work has suggested that the aforementioned three properties
might be a more universal feature of neural population codes [16]. In
particular, brain regions such as MT and V1, which have similar firing rates
and pairwise correlations to the retinal ganglion cells, were hypothesized to
have these same properties in their neural codes. A more general framework in
which to talk about neural population codes with these three properties is
therefore desirable, especially if it can make predictions to specific
structures that these codes should have.

The rest of this paper will focus on such a framework. In the Method section,
we outline our model for mapping arbitrary neural population responses to
codewords. Our model utilizes the universal property of free groups (UPFG). We
then provide an example of our model by mapping a specific set of neural
responses to a given set codewords. We compare our methods mapping with the
mapping generated by using Generalized Minimum Distance (GMD) decoding [17], a
well known method in coding theory. This example is given to provide a more
intuitive feel for our model (especially for those unfamiliar with group
theory) and illustrate how it compares to other known (but not directly
implicated in neural population coding) error correction algorithms. Finally,
in the Discussion section, we discuss the implications of our model with
regards to real neural population data and possible future directions for this
work.

## Why use the UPFG?

There are two reasons why we turn to using such a formal, and mathematically
abstract, language as group theory for this problem. First, for those with a
background in group theory, we believe that our model is fairly intuitive.
Second, and more pertinently, theoretical neuroscience has seen great advances
when appropriate theories/descriptions from formal physics and mathematics
have been applied to neural problems. For instance, by borrowing ideas and
analysis techniques from statistical physics, attractor neural networks (ANNs)
were able to be developed and thoroughly explored [18], [19]. In this vein, we
feel that when considering redundant neural codes that “collapse” different
population response states onto the same output (or recognized) state, the
theory associated with homomorphisms (and group theory), is an appropriate
language to use. For those unfamiliar with group theory, see some basic
discussion in the Material and Methods section for a brief discussion of the
simple group theoretic definitions and notions used in our model.

## Model

We start by defining the set of generators, $G$, as $G=S+B$, where
$S=\\{1,2,...,n\\}$, $B$ is a subset of the power set of $S$ (i.e.
$B\subset\mathcal{P}(S)$), and $+$ is the set concatenation operator. We refer
to $B$ as the basis set. The relevance of $B$ will be discussed below.

A simple example of this is, for $n=5$, $G=\\{1,2,3,4,5,12,145\\}$, where the
last two elements are the elements of the basis set (here $12$ stands for
$\\{1,2\\}$).

We define the group of codewords, $(C,*_{C})$, as
$C=\\{c_{1},c_{2},...,c_{m}\\}$ and $*_{C}$ is some operation on the elements
of $C$ that meets the standard group criteria [20].

Finally, the restricted free group of G, $\tilde{F}(G)$, is defined to be the
abeleanized group of all elements in the free group of $G$, $F(G)$, that are
made up of, at most, each element of $G$ once. For instance, while $121\in
F(G)$, $121\notin\tilde{F}(G)$ because it has $1$ twice.

Using the universal property of free groups [20], we have the following
diagram,

${G}$${F(G)}$${C}$$i$$g$$\varphi$ (1)

where $i$ is the inclusion map (i.e. $i(x)=x$ for all $x\in G$), $g$ is a
group function determining $C$ from $G$, and $\varphi$ is a unique
homomorphism (given a specific $g$) from $F(G)$ to $C$. The UPFG tells us that
we can relate $g$ to $\varphi$ by

$\varphi(A)=g(a_{1})*_{C}...*_{C}g(a_{n})$ (2)

where $A\in F(G)$ and $A=a_{1}...a_{n}$, such that $a_{i}\in G$ for all $1\leq
i\leq n$.

A final point on our model must be made. We define, for all $s\in S$,

$g(s)=\text{id}_{C}$ (3)

where idC is the identity element of the group of code words (i.e. for all
$a\in C$, $a\hskip 2.84526pt*_{C}$ id${}_{C}=a$).

With this definition, it is more clear what the role of the basis set, $B$, is
(as it is unnecessary for “building” $F(G)$); it is the generator of
$(C,*_{C})$ under $g$.

We now consider an element (or “word”), $\omega$, of $\tilde{F}(G)$ (we
consider $\tilde{F}(G)$ because of it represents all possible neural responses
that were considered in the neural data from [12] \- [15], but the same holds
true, with small modifications, for any element in $F(G)$). We want to find
the codeword (i.e. the element in $(C,*_{C})$ that corresponds to $\omega$. In
particular, for any given $\omega$, there exists a subset of $B$,
$\\{b_{1},...,b_{k}\\}$, and a subset of $S$, $\\{s_{1},..,s_{m}\\}$
($s_{j}\in S$), s.t.

$\omega=b_{1}...b_{k}s_{1}...s_{m}$ (4)

(the exact ordering of the $b_{i}$’s and $s_{j}$’s doesn’t matter because
$\tilde{F}(G)$ is abelian). Of course, this decomposition of $\omega$ is by no
means unique. We therefore define the decomposition of $\omega$ as the pair
$(\\{b_{i}\\},\\{s_{j}\\})$, s.t. the number of elements of $\\{b_{i}\\}$ is
the (if possible) non-zero minimum of all the possible decompositions of
$\omega$. From the neural perspective, this is equivalent to demanding that
every word is represented as simply as possible by the activity states that
make up the basis set.

With this, we can now look at the mapping of $\omega$ to its relevant
codeword, which is given by $\varphi(\omega)$ (since
$\varphi:\tilde{F}(G)\rightarrow C$).

$\varphi(\omega)=\varphi(b_{1}...b_{k}s_{1}...s_{l})$ (5)
$=g(b_{1})*_{C}...*_{C}g(b_{k})*_{C}g(s_{1})*_{C}...*_{C}g(s_{l})$
$=g(b_{1})*_{C}...*_{C}g(b_{k})$

By the defined decomposition of $\omega$, this decoding is unique.

Note therefore that if two elements, $\omega_{1}$ and $\omega_{2}$, in
$\tilde{F}(G)$ have the same basis elements, $\\{b_{i}\\}$, in their
decomposition, then the decoding of the two elements is equivalent

$\varphi(\omega_{1})=g(b_{1})*_{C}...*_{C}g(b_{k})=\varphi(\omega_{2})$ (6)

### Example

To illustrate our model, we map an example neural response space onto to
example codewords. We also compare this mapping to an existing error
correction method, Generalized Minimal Distance (GMD) decoding [17], as a way
to show the possible strengths of our method in reference to existing methods.

We will consider $G=\\{1,2,3,4,12,24\\}$,
$C=\big{(}\\{0,12,24,14\\},+\big{)}$. For simplicity, we will convert each
element of $G$ and $C$ into a binary string. This corresponds to
$G=\\{1000,0100,0010,0001,1100,0101\\}$ and
$C=\big{(}\\{0000,1100,0101,1001\\},+$ $\text{mod(2)}\big{)}$, if we take each
number, $1,..,4$, to be a position in a four bit string that has a value of
$1$.

The result of applying our mapping method and applying GMD decoding (where the
decoding is determined by the codeword that has the minimal Hamming distance
from the word we are trying to decode) is given in Table 1. Note that we are
assuming that every word is equally likely to be received. From this, we see
that, first and foremost, the number of three way ties (as denoted by $?$) is
significantly less using the UPFG decoding as opposed to GMD decoding (one vs.
eight). Additionally, in every determined decoding, the two methods agree.

Table 1: Comparison of our model (UPFG mapping) and GMD decoding on an example response space Word | UPFG decoding | GMD decoding
---|---|---
1111 | ? | ?
1110 | 1100 | 1100
1101 | 1100 | ?
1011 | 1001 | 1001
0111 | 0101 | 0101
1100 | 1100 | 1100
1001 | 1001 | 1001
0011 | 0000 | ?
1010 | 0000 | ?
0101 | 0101 | 0101
0110 | 0000 | ?
1000 | 0000 | ?
0100 | 0000 | ?
0010 | 0000 | 0000
0001 | 0000 | ?
0000 | 0000 | 0000
Table 2:

## Discussion

Recent work investigating the structure of the retinal ganglion and glomeruli
population codes, [12] \- [15], has challenged a number of widely held
theoretical biophysical and neural beliefs with their three central (and
convergent) conclusions: the respective neural population codes are redundant,
in the sense that multiple neural response states are interpreted as encoding
the same information; it is the identity of the relevant subset of neurons
that fire, and not the relative timing of their firing, that encodes the
identity of the stimulus; such codes with the previous two properties are
endowed with the capability of error correction.

The fact that these neural population codes were found to be redundant
contradicts the belief that neural codes should be very efficient. Such
conclusions will force theorists to reconsider what, if anything, neural
population codes are optimized for. Additionally, the finding that the first
two properties allow for error correction marks a transition from the focus of
biophysical and neural theory on how systems can output robustly despite noise
(for a few of many examples, see [21], [22], [23], [24]) to the idea that the
output of neural systems can be noisy, but it is the subsequent mapping (or
“interpretation”) of that output that is robust to noise.

Finally, that these conclusions are reached by very different experimental and
theoretical methods in the retinal ganglion and glomeruli populations suggest
that the two sensory systems (vision and olfaction), despite being previously
believed to be operating under different coding principles, are, in fact,
using the same principles. This surprising (and powerful) fact, coupled with
theoretical work [16] arguing that these coding principles might be used in
more than just early sensory systems, and in higher brain areas like MT and
V1, highlights the need for a general framework in which to discuss codes with
such three properties.

To see that our model indeed is a general framework that meets all three of
these facets of neural population codes, note first that it is only the basis
elements that determine the decoding of any word. Therefore, words that vary
by elements that don’t affect the basis elements are seen as equivalent (i.e.
eq. 6). This can also be clearly seen in Table 1 (e.g. 1100 and 1101 have the
same mapping). Second, the fact that we restrict ourselves to looking
specifically at the restricted free group of $G$, $\tilde{F}(G)$, we are not
only restricting ourself to the more reasonable neural case where neurons are
consider to have fired at most once in a time bin, we are also restricting
ourselves to only the identity of the basis elements mattering in decoding and
not the ordering, as $\tilde{F}(G)$ is abelian, and hence, the words
$\omega_{1}\omega_{2}$ and $\omega_{2}\omega_{1}$ are equivalent. Finally, as
noted before, because only the basis elements in the decomposition of a given
word determine the decoding, our method is capable of error correction.

Our model, while capturing the three main principles of the aforementioned
work, also makes predictions about aspects of the early sensory systems’
coding. In particular it predicts the existence of a basis set. In the context
of the glomeruli population code, there exist two possibilities. Either one,
$n$ (the number of relevant active glomeruli for odor classification) is fixed
and the basis set is the set of codewords, which gives no new insight into the
code. If $n$ is not fixed, then there exists the possibility of all codewords
being able to be built from some smaller set of response states that are
themselves codewords. For example, if $n=2,3,$ and $4$ are all allowed (e.g.
$n$ is a function of odor complexity), then any $n=4$ codeword could be built
from two codewords that are $n=2$. This greatly reduces the amount of elements
needed for describing the codewords, and sheds light onto possible downstream
decoding mechanisms.

Similarly, for the retinal population code, the existence of a non-trivial
basis set would shed light on downstream decoding schemes. In particular, it
would provide possible adjustments to the model hypothesized in [13] (i.e.
Fig. 13). It is important to note that looking for the basis set in the
retinal population code may require a switch in perspective, where it is the
neurons in a given codewords silent set that might be the relevant feature.
Future work will focus on methods for searching for basis sets, as well as
specific implications of the existence of basis sets for downstream decoding
schemes and how such schemes might develop in a natural way. Finding such
basis sets in both the glomeruli and retinal population codes would extend
even further the growing understanding of how similar the two codes are, and
provide more evidence for the two operating under more universal computing
principles.

One clear failure of our model is that is relies on group theoretic notions
that most in the neuroscience community aren’t familiar with. While we believe
that continuing to think in terms of this language will be useful (and indeed,
we hope that our model convinces others in the mathematical community to
consider the possible role free groups, and the UPFG, might play in error
correction and neural coding), we hope to translate this model into a more
clear, and less mathematically technical, model that still captures the main
principles, but can more easily be communicated to others.

We hope that we have made clear the similarities of the two early sensory
systems’ population codes, the need for a general framework in which to
explore arbitrary codes that share the properties exhibited by those two
codes, and the possible utility of using group theory as a language to talk
about such codes.

### Materials and Methods

We provide here the basic group theory definitions and notions that are
required for understanding our model. We have tried to make this as easy to
understand as possible for the reader not familiar with group theory. Note
that therefore some of the extra complications or subtleties are swept under
the rug at the discretion of the author, especially if they are not believed
to be relevant for understanding our model. Everything written below can be
found in the following two references [20], [25].

### Groups

A group is defined as the pair $(G,*_{G})$, where $G$ is a set of elements and
$*_{G}$ is a binary operation that satisfies the following three properties:

  1. 1.

There exists an identity element in $G$ under $*_{G}$. That is, there is an
element idG such that id${}_{G}*_{G}x=x$ for all $x\in G$.

  2. 2.

The elements of $G$ are self contained under $*_{G}$. That is, for all $x,y\in
G$, $(x*_{G}y)\in G$.

  3. 3.

There exists an inverse element for all elements of $G$. That is, for all
$x\in G$, there exists $x^{-1}$ such that $x*_{G}x^{-1}=$ idG.

An example of a group is the integers under addition. It is easily verified
that all three conditions are met, where the identity element is $0$ and the
inverse of $n$ is $-n$.

For simplicity, groups will now be referred to as just $G$, where $*_{G}$ is
implicitly assumed.

### Abelian

A group is said to be abelian if the elements of $G$ commute. That is, if for
all $x,y\in G$, $x*_{G}y=y*_{G}x$.

For the integers under addition, this is clearly the case. But most groups are
not abelian (e.g. the set of matrices with unit eigenvalues under matrix
multiplication are not abelian).

### Homomorphisms

A homomorphism is a map, $\varphi$, between two groups, $G$ and $H$, such that
$\varphi(x*_{G}y)=\varphi(x)*_{H}\varphi(y)$ for all $x,y\in G$. Note that the
binary operations are different on each side of the equation.

In simpler terms, a homomorphism is a map that collapses one group onto
another, while preserving some structure. For instance, the parity map (i.e.
the map that returns $0$ if the argument is even and $1$ if the argument is
odd), $\varphi$, from the integers to the integers modulus $2$ (i.e.
$(\\{0,1\\},+\text{mod}(2))$, where $1+1=0$ mod$(2)$) is a homomorphism.
$\varphi$ clearly collapses the integers (it reduces them to a set with only
two elements), but it preserves some structure (namely, parity).

### Free groups

A free group, $F(G)$, is an infinite group (in the sense that the set that
comprises the elements of the free group is infinite) that is comprised of
every possible combination of the elements of the set $G$, using the binary
operation $*$. For instance, if $G=\\{a,b,a^{-1},b^{-1}\\}$, then the set
comprising $F(G)$ is given by
$\\{a,b,a*a,a*b,b*a,a^{-1}*b,a*b^{-1},a^{-1}*b^{-1},a*a*a,...\\}$.

### Acknowledgements

We thank Sylvain Cappell for introducing us to free groups and for his clear
explanation of the UFPG, Sanchit Chaturvedi and Roy Rinberg for their
insightful discussions, and Nick Verga for inviting us to present our work
early on. Finally, we thank Michael Berry and Dima Rinberg for discussing
their work with us.

## References

  * [1] Berry M, Warland D, Meister M (1997) The structure and precision of retinal spike trains. Proc. Natl. Acad. Sci.
  * [2] Schneidman E, Berry II M, Segev R, Bialek W (2006) Weak pairwise correlations imply strongly correlated network states in a neural population. Nature.
  * [3] Tkacik G, et al. (2014) Searching for collective behavior in a large network of sensory neurons. PLoS Computational Biology.
  * [4] Tkacik G, et al. (2015) Thermodynamics and signatures of criticality in a network of neurons. Proc. Natl. Acad. Sci.
  * [5] Mora T, Deny S, Marre O (2015) Dynamical criticality in the collective activity of a population of retinal neurons. Physics Review Letters.
  * [6] Gross-Isseroff R, Smith B (1988) Concentration-dependent changes of percieved odor quality. Chem. Senses.
  * [7] Bhagavan S, Smith B (1997) Olfactory conditioning in the honey bee, apis mellifera: effects of odor intensity. Physiol. Behav.
  * [8] Uchida N, Mainen Z (2007) Odor concentration invariance by chemical ratio coding. Front. Syst. Neurosci.
  * [9] Cleland T, et al. (2011) Sequential mechanisms underlying concentration invariance in biological olfaction. Front. Neuroeng.
  * [10] Malnic B, Hirono J, Sato T, Buck LB (1999) Combinatorial receptor codes for odors. Cell.
  * [11] Saito H, Chi Q, Zhuang H, Matusnami H, Mainland JD (2009) Odor coding by a mammalian receptor repertoire. Sci. Signal.
  * [12] Prentice J, et al. (2016) Error-robust modes of the retinal population code. PLoS Computational Biology.
  * [13] Loback A, Prentice J, Ioffe M, Berry II M (2017) Noise-robust modes of the retinal population code have the geometry of “ridges” and correspond to neuronal communities. Neural Computation 29(12):3119–3180.
  * [14] Wilson C, Serrano G, Koulakov A, Rinberg D (2017) A primacy code for odor identity. Nature communications 8(1).
  * [15] Giaffar H, Rinberg D, Koulakov A (2018) Primacy model and the evolution of the olfactory receptor repertoire. bioRxiv.
  * [16] Ioffe M, Berry II M (2017) The structured ‘low temperature’ phase of the retinal population code. PLoS Computational Biology.
  * [17] Forney G (1996) Generalized minimum distance decoding. IEEE Transactions on Information Theory.
  * [18] Hopfield J (1982) Neural networks and physical systems with emergent collective computational abilities. Proc. Natl. Acad. Sci.
  * [19] Amit D (1989) Modeling Brain Function: The World of Attractor Neural Networks. (Cambridge University Press).
  * [20] Dummit D, Foote R (1991) Abstract Algebra. (Prentice Hall, Engelwood Cliffs, N.J.).
  * [21] Wolpert L (1969) Positional information and the spatial pattern of cellular differentiation. J. Theor. Biol.
  * [22] Gregor T, Tank D, Wieschaus E, Bialek W (2007) Probing the limits to positional information. Cell.
  * [23] Elowitz M, Levine A, Siggia E, Swain P (2002) Stochastic gene expression in a single cell. Science.
  * [24] Losick R, Desplan C (2008) Stochasticity and cell fate. Science.
  * [25] Herstein IN (1975) Topics in Algebra. (John Wiley & Sons), 2 edition.