11institutetext: School of Electronic and Information Engineering, Nanjing
University of Information Science & Technology, Nanjing, China
11email<EMAIL_ADDRESS>
# Stroke Lesion Segmentation with Visual Cortex Anatomy Alike Neural Nets

Chuanlong Li

###### Abstract

Cerebrovascular accident, or commonly known as stroke, is an acute disease
with extreme impact on patients and healthcare systems and is the second
largest cause of death worldwide. Fast and precise stroke lesion detection and
location is an extreme important process with regards to stroke diagnosis,
treatment, and prognosis. Except from the manual segmentation approach,
machine learning based segmentation methods are the most promising ones when
considering efficiency and accuracy, and convolutional neural network based
models are the first of its kind. However, most of these neural network models
do not really align with the brain anatomical structures. Intuitively, this
work presents a more brain alike model which mimics the anatomical structure
of the human visual cortex. Through the preliminary experiments on the stroke
lesion segmentation task, the proposed model is found to be able to perform
equally well or better to the de-facto standard U-Net. Part of the
implementation will be made available at https://github.com/DarkoBomer/VCA-
Net.

##  1 Introduction

According to the World Health Organization (WHO), cerebrovascular accident is
a world disease with extreme impact on patients and healthcare systems and is
the second largest cause of death worldwide [12][11]. Fast and precise stroke
lesion detection and segmentation is an extreme important process with regards
to stroke diagnosis, treatment, and prognosis. Except from the manual
segmentation approach, machine learning based segmentation methods are the
most promising ones when considering efficiency and accuracy, and
convolutional neural network based models are the first of its kind
[25][32][29][30][33][17]. However, these neural network models do not really
align with the brain anatomical structures thus lack of explanatory
characteristics of the model outcomes. This work draws inspiration from
neuroscience world and presents a brain alike model which mimics the
anatomical structure of the human visual cortex, aiming to facilitate the
stroke diagnosis and improve the healthcare systems by giving a more intuitive
and explainable computational model.

##  2 Methodology

U-Net has been the mostly adopted base network for most of the deep learning
methods. The U-shape with skip connections is able to capture both low and
high level features and has become the de-facto standard for most deep
learning based segmentation networks [24]. Many stroke lesion segmentation
networks has been proposed since then
[27][21][28][29][34][15][7][4][31][35][3][23][22]. In terms of brain-like
neural nets, Kubilius et al. demonstrated that better anatomical alignment to
the brain of deep learning networks could achieve high performance in image
recognition tasks [10]. Alekseev et al. proposed an image recognition system
by using a learnable Gabor Layer inside the deep convolutional neural network
[1], since Gabor filter is able to effectively extract spacial frequency
structures from images and represent texture features.

###  2.1 Modeling

This work proposes to construct a visual cortex anatomy alike model to
simulate the process of identifying the stroke lesion using human vision
system. The model is simulated as a deep neural network follows the anatomical
structure of the human visual cortex. The visual cortex processes visual
information inside human brain by transmitting visual information into two
primary pathways, known as the ventral stream and the dorsal stream [19]. The
ventral stream is associated with object representation, form recognition, and
storage of long-time memory. The dorsal stream is associated with motion and
representation of object locations. This work only considers the ventral steam
and models the ventral anatomical structure considering the characteristics of
this specific segmentation task. An overview of the computational segmentation
modeling of visual cortex is illustrated in Figure 1.

Figure 1: Computational modeling of the visual cortex anatomy (The ventral
stream begins with V1, goes through visual area V2, then through visual area
V4, and to the inferior temporal cortex)

The primary visual cortex (V1) consists of six functionally distinct layers
and layer 4 is further divided into 4 separate layers [8]. The receptive field
of neurons in V1 is typically smaller compared to other visual cortex
microscopic regions. In view of the structure and functionality of the primary
visual cortex, the V1 area is modeled as a customized sets of layers. It is
constructed with 6 convolutional blocks and the fourth block is further
divided into 4 parallel layers Figure 2.

Figure 2: V1 Block

Visual area V2 is the second major area in the visual cortex. It receives
feedforward connections from V1 while sending feedbacks to V1, and further
sends connections to V3, V4, and V5 [26]. V2 contains a dorsal and ventral
representation in the left and the right hemispheres and cells are tuned to
simple properties including orientation, spatial frequency, and color, like V1
structure. In view of the common properties between V1 and V2 and the
anatomical structure of V2 area, V2 is modeled as a 4 parallel-layers module
Figure 3.

Figure 3: V2 Block

Visual area V4 is located anterior to V2 and posterior to the posterior
inferotemporal area (PIT). It receives strong feedforward input from V2 and
also receives direct input from V1 [5]. V4 is also tuned for orientation,
spatial frequency, and color and is the first area in the ventral stream to
show strong attentional modulation. V4 is further tuned for object features of
intermediate complexity. V4 is computationally modeled as a simple stack of
layers but accepts two inputs which represents the intermediate input from V2
and direct input from V1 Figure 4.

Figure 4: V4 Block

The IT cortex in humans is located to a specific region of the human temporal
lobe [2][16]. It processes visual stimuli of objects and is involved with
memory and memory recall to identify specific objects [20]. It processes
visual stimuli from V1, V2, V3, and V4 regions of the occipital lobe [6] by
identifying the object based on the color and form and comparing that
processed information to stored memories of objects to identify specific
object [9]. IT cortex is designed to amplify the features calculated by
previous areas. IT area is modeled as a more complicated block of layers
compared to other areas Figure 5, first it accepts three separate inputs
corresponding to V1, V2, and V4 intermediate outputs. After transforming these
three inputs through custom convolutional blocks, the transformed $v_{1}$ and
$v_{2}$ will be merged and the merged results will further be merged with the
transformed $v_{4}$ inputs into $v_{m}$. Finally, the transformed $v_{4}$ will
go through a dilated convolutional block and then be concatenated with the
merged results $v_{m}$. This intermediate results will serve as the IT
bottleneck and further be followed by 4 UpSampling blocks to output the final
prediction. The kernel size of IT module is typically larger than previous
areas.

Figure 5: IT Bottleneck

###  2.2 Training Strategy

Stroke lesion varies in size and shape, which makes it hard to predict. Also
in a supervised context, the target lesion mask samples are usually far less
than the normal samples which makes it even hard to train. This paper utilizes
the EMLLoss function proposed by [35] and combines it with the Binary Cross
Entropy Loss. The EMLLoss is constructed with Focal Loss and Dice Loss. Focal
Loss is proposed by [14] to alleviate the extreme data imbalance issue. Dice
Loss is derived from the Dice Similarity Coefficient which measures the
similarity between two sample sets [18].

$DSC=\frac{2TP}{2TP+FP+FN}$ (1)

$\displaystyle Loss$ $\displaystyle=EMLLoss+BCELoss$ (2)
$\displaystyle=\frac{-\alpha_{t}(1-p_{t})^{\gamma}log(p_{t})}{N}+log(1-DSC)+BCELoss$

##  3 Experiments

###  3.1 Implementation

####  3.1.1 Neural Nets

The V1 module consists of a six-layer basic convolution block. Each basic
convolution block is formed by sequentially lining up a convolutional layer, a
BatchNormalization layer, and a LeakyReLU activation layer (Conv-BN-LReLU).
The kernel size of the first, third, and fifth convolutional layer of V1 is
set to 3 with a stride of 1. The kernel size of the second, sixth layer is set
to 1 with a stride of 1. The fourth layer is an InceptionE alike module with
different in-out channels setup and the V2 module is an InceptionA alike
module with different in-out channels setup. The V4 module consists of two
branches, the first branch stacks two Conv-BN-LReLU blocks with convolutional
kernel size of 3 and 1 respectively; the second branch is a single Conv-BN-
LReLU block with convolutional kernel size of 1. The IT module consists a IT
bottleneck block and a UpSampling block. The IT bottleneck is constructed with
four Conv-BN-LReLU blocks with kernel size and stride setting to 5(stride=2),
5(2), 3(1), 3(padding=2, stride=1, dilation=2), respectively. Each of them
corresponds to a transform of the corresponding inputs $v_{1}$, $v_{2}$,
$v_{4}$, and $v_{m}$. Four UpSampling blocks are appended after to restore the
intermediate feature maps into the original resolution. Skip connections
between each stage are also implemented in this task.

The SGD optimizer is used with an initial learning rate of 0.001, a weight
decay of 1e-8 and a momentum of 0.9. The batch size is set to 8 due to the
limitation of the GPU memory. All network code are written in Python using
PyTorch framework and the model was trained using one NVIDIA GTX2080Ti GPU. A
prototype stroke imaging application on iOS is also developed to facilitate
the usage of the model. The stroke imaging application has been tested on an
iPhone 11 and an iPhone 7 plus model and performs well. Details could be seen
in Figure 6.

Figure 6: Prototype system on iOS

####  3.1.2 Dataset

The Anatomical Tracings of Lesions After Stroke (ATLAS) dataset is used in
this work [13]. The ATLAS dataset contains 229 T1-weighted MRI images and each
volume contains 189 axial slices and each slice is of size 233x197. All axial
image slices are resized into size of 224x192 and a split of 9:1 of all the
preprocessed axial slices is used during the training process.

###  3.2 Analysis

####  3.2.1 Metrics

In a disease context, true positive (TP) stands for correctly diagnosed as
diseased; false positive (FP) stands for incorrectly diagnosed as diseased;
true negative (TN) stands for correctly diagnosed as not diseased; false
negative (FN) stands for incorrectly diagnosed as not diseased. Jaccard Index
(IoU) and Dice similarity coefficient (F1 score) are both used to measure the
similarity of two sets, the mathematical representations can be written using
the definition of TP, FP, and FN:

$F_{1}=\frac{2*precision*recall}{precision+recall}=\frac{TP}{TP+\frac{1}{2}(FP+FN)}$
(3)

$J(A,B)=\frac{A\cap B}{A\cup B}=\frac{A\cap B}{|A|+|B|-|A\cap B|}$ (4)

Sensitivity (recall, true positive rate), refers to the proportion of positive
cases that are correctly identified:

$SENSITIVITY=\frac{TP}{TP+FN}$ (5)

Precision (positive predictive value), measures the fraction of positive cases
among the retrieved instances:

$PRECISION=\frac{TP}{TP+FP}$ (6)

The Hausdorff distance is the greatest of all the distances from a point in
one set to the closest point in the other set. It measures the distance
between two subsets of a certain metric space:

$d_{H}(X,Y)=\mathrm{max}\\{\mathop{\mathrm{sup}}\limits_{x\in
X}d(x,Y),\mathop{\mathrm{sup}}\limits_{y\in Y}d(X,y)\\}$ (7)

####  3.2.2 Results

Some of the tested images from the ATLAS dataset are shown in Figure 7. State-
of-the-art performance is not the goal of this work as the intention is to
model the network follows the visual cortex anatomy so as to demonstrate the
neuroscience intuition. Still, the proposed model can perform comparably to
the de-facto standard U-Net Table 1.

Figure 7: Segmentation examples on the ATLAS dataset Table 1: Evaluation metrics on the ATLAS dataset (Slice-to-Slice) Method | DSC | IoU | HD | Sensitivity | Precision | F1 Score
---|---|---|---|---|---|---
U-Net | 0.8806 | 0.2935 | 22.0066 | 0.3508 | 0.4457 | 0.3687
Proposed | 0.8449 | 0.3379 | 32.9180 | 0.4296 | 0.5349 | 0.4454

##  4 Discussions

Stroke lesion segmentation is a very challenging task considering its nature.
This paper proposes a computational model which utilizes neural networks to
resemble the anatomical structure of the visual cortex. This research is
conducted primarily by demonstrating how neural networks should be designed
from a neuroscience point of view, which could bring a more explanatory model
for doctors and physicians thus putting more trust into the computational
models, which could further facilitate the usage of the models and be of real-
world assistance. However, this work is just a preliminary research and only
considers part of the anatomical structure of the visual cortex. To further
improve the model and research on this area, more complex brain anatomical
connections and functionalities of the brain areas should be considered into.
Sophisticated net structures should also be meticulously designed.

## Acknowledgments

This work was supported by the Postgraduate Research & Practice Innovation
Program of Jiangsu Province (Grant KYCX20_0934). The author would like to
thank Dr. David S. Liebeskind and Dr. Fabien Scalzo for their inspirations and
thoughtful insights, and Dr. Xingming Sun for providing the infrastructure
resources for the experiments to be conducted smoothly.

## References

  * [1] Alekseev, A., Bobe, A.: Gabornet: Gabor filters with learnable parameters in deep convolutional neural network. In: 2019 International Conference on Engineering and Telecommunication (EnT). pp. 1–4. IEEE (2019)
  * [2] Chelazzi, L., Miller, E.K., Duncan, J., Desimone, R.: A neural basis for visual search in inferior temporal cortex. Nature 363(6427), 345–347 (1993)
  * [3] Clèrigues, A., Valverde, S., Bernal, J., Freixenet, J., Oliver, A., Lladó, X.: Acute and sub-acute stroke lesion segmentation from multimodal mri. Computer methods and programs in biomedicine 194, 105521 (2020)
  * [4] Dolz, J., Ayed, I.B., Desrosiers, C.: Dense multi-path u-net for ischemic stroke lesion segmentation in multiple image modalities. In: International MICCAI Brainlesion Workshop. pp. 271–282. Springer (2018)
  * [5] Goddard, E., Mannion, D.J., McDonald, J.S., Solomon, S.G., Clifford, C.W.: Color responsiveness argues against a dorsal component of human v4. Journal of Vision 11(4), 3–3 (2011)
  * [6] Gross, C.G.: Representation of visual stimuli in inferior temporal cortex. Philosophical Transactions of the Royal Society of London. Series B: Biological Sciences 335(1273), 3–10 (1992)
  * [7] Ho, K.C., Speier, W., Zhang, H., Scalzo, F., El-Saden, S., Arnold, C.W.: A machine learning approach for classifying ischemic stroke onset time from imaging. IEEE transactions on medical imaging 38(7), 1666–1676 (2019)
  * [8] Hubel, D.H., Wiesel, T.N.: Laminar and columnar distribution of geniculo-cortical fibers in the macaque monkey. Journal of Comparative Neurology 146(4), 421–450 (1972)
  * [9] Kolb, B., Whishaw, I.Q., Teskey, G.C.: An introduction to brain and behavior. Worth New York (2001)
  * [10] Kubilius, J., Schrimpf, M., Kar, K., Hong, H., Majaj, N.J., Rajalingham, R., Issa, E.B., Bashivan, P., Prescott-Roy, J., Schmidt, K., et al.: Brain-like object recognition with high-performing shallow recurrent anns. arXiv preprint arXiv:1909.06161 (2019)
  * [11] Lee, E.J., Kim, Y.H., Kim, N., Kang, D.W.: Deep into the brain: artificial intelligence in stroke imaging. Journal of stroke 19(3), 277 (2017)
  * [12] Leslie-Mazwi, T.M., Lev, M.H.: Towards artificial intelligence for clinical stroke care. Nature Reviews Neurology 16(1), 5–6 (2020)
  * [13] Liew, S.L., Anglin, J.M., Banks, N.W., Sondag, M., Ito, K.L., Kim, H., Chan, J., Ito, J., Jung, C., Khoshab, N., et al.: A large, open source dataset of stroke anatomical brain images and manual lesion segmentations. Scientific data 5(1), 1–11 (2018)
  * [14] Lin, T.Y., Goyal, P., Girshick, R., He, K., Dollár, P.: Focal loss for dense object detection. In: Proceedings of the IEEE international conference on computer vision. pp. 2980–2988 (2017)
  * [15] Liu, L., Chen, S., Zhang, F., Wu, F.X., Pan, Y., Wang, J.: Deep convolutional neural network for automatically segmenting acute ischemic stroke lesion in multi-modality mri. Neural Computing and Applications pp. 1–14 (2019)
  * [16] Logothetis, N.K., Pauls, J., Poggio, T.: Shape representation in the inferior temporal cortex of monkeys. Current biology 5(5), 552–563 (1995)
  * [17] Long, J., Shelhamer, E., Darrell, T.: Fully convolutional networks for semantic segmentation. In: Proceedings of the IEEE conference on computer vision and pattern recognition. pp. 3431–3440 (2015)
  * [18] Milletari, F., Navab, N., Ahmadi, S.A.: V-net: Fully convolutional neural networks for volumetric medical image segmentation. In: 2016 fourth international conference on 3D vision (3DV). pp. 565–571. IEEE (2016)
  * [19] Mishkin, M., Ungerleider, L.G., Macko, K.A.: Object vision and spatial vision: two cortical pathways. Trends in neurosciences 6, 414–417 (1983)
  * [20] Miyashita, Y.: Inferior temporal cortex: where visual perception meets memory. Annual review of neuroscience 16(1), 245–263 (1993)
  * [21] Mondal, A.K., Dolz, J., Desrosiers, C.: Few-shot 3d multi-modal medical image segmentation using generative adversarial learning. arXiv preprint arXiv:1810.12241 (2018)
  * [22] Pedemonte, S., Bizzo, B., Pomerantz, S., Tenenholtz, N., Wright, B., Walters, M., Doyle, S., McCarthy, A., De Almeida, R.R., Andriole, K., et al.: Detection and delineation of acute cerebral infarct on dwi using weakly supervised machine learning. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. pp. 81–88. Springer (2018)
  * [23] Qi, K., Yang, H., Li, C., Liu, Z., Wang, M., Liu, Q., Wang, S.: X-net: Brain stroke lesion segmentation based on depthwise separable convolution and long-range dependencies. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. pp. 247–255. Springer (2019)
  * [24] Ronneberger, O., Fischer, P., Brox, T.: U-net: Convolutional networks for biomedical image segmentation. In: International Conference on Medical image computing and computer-assisted intervention. pp. 234–241. Springer (2015)
  * [25] Scalzo, F., Nour, M., Liebeskind, D.S.: Data science of stroke imaging and enlightenment of the penumbra. Frontiers in neurology 6, 8 (2015)
  * [26] Schwarzkopf, D.S., Song, C., Rees, G.: The surface area of human v1 predicts the subjective experience of object size. Nature neuroscience 14(1), 28–30 (2011)
  * [27] Seo, H., Badiei Khuzani, M., Vasudevan, V., Huang, C., Ren, H., Xiao, R., Jia, X., Xing, L.: Machine learning techniques for biomedical image segmentation: An overview of technical aspects and introduction to state-of-art applications. Medical physics 47(5), e148–e167 (2020)
  * [28] Sharique, M., Pundarikaksha, B.U., Sridar, P., Krishnan, R.R., Krishnakumar, R.: Parallel capsule net for ischemic stroke segmentation. bioRxiv p. 661132 (2019)
  * [29] Stier, N., Vincent, N., Liebeskind, D., Scalzo, F.: Deep learning of tissue fate features in acute ischemic stroke. In: 2015 IEEE international conference on bioinformatics and biomedicine (BIBM). pp. 1316–1321. IEEE (2015)
  * [30] Tan, C., Guan, Y., Feng, Z., Ni, H., Zhang, Z., Wang, Z., Li, X., Yuan, J., Gong, H., Luo, Q., et al.: Deepbrainseg: Automated brain region segmentation for micro-optical images with a convolutional neural network. Frontiers in neuroscience 14 (2020)
  * [31] Valverde, S., Salem, M., Cabezas, M., Pareto, D., Vilanova, J.C., Ramió-Torrentà, L., Rovira, À., Salvi, J., Oliver, A., Lladó, X.: One-shot domain adaptation in multiple sclerosis lesion segmentation using convolutional neural networks. NeuroImage: Clinical 21, 101638 (2019)
  * [32] Vincent, N., Stier, N., Yu, S., Liebeskind, D.S., Wang, D.J., Scalzo, F.: Detection of hyperperfusion on arterial spin labeling using deep learning. In: 2015 IEEE International Conference on Bioinformatics and Biomedicine (BIBM). pp. 1322–1327. IEEE (2015)
  * [33] Yu, Y., Parsi, B., Speier, W., Arnold, C., Lou, M., Scalzo, F.: Lstm network for prediction of hemorrhagic transformation in acute stroke. In: International Conference on Medical Image Computing and Computer-Assisted Intervention. pp. 177–185. Springer (2019)
  * [34] Zhao, B., Ding, S., Wu, H., Liu, G., Cao, C., Jin, S., Liu, Z.: Automatic acute ischemic stroke lesion segmentation using semi-supervised learning. arXiv preprint arXiv:1908.03735 (2019)
  * [35] Zhou, Y., Huang, W., Dong, P., Xia, Y., Wang, S.: D-unet: a dimension-fusion u shape network for chronic stroke lesion segmentation. IEEE/ACM transactions on computational biology and bioinformatics (2019)


# Junta threshold for low degree Boolean functions on the slice

Yuval Filmus

###### Abstract

We show that a Boolean degree $d$ function on the slice $\binom{[n]}{k}$ is a
junta if $k\geq 2d$, and that this bound is sharp. We prove a similar result
for $A$-valued degree $d$ functions for arbitrary finite $A$, and for
functions on an infinite analog of the slice.

##  1 Introduction

A classical result of Nisan and Szegedy [NS94] states that a Boolean degree
$d$ function on the Boolean cube $\\{0,1\\}^{n}$ is an $O(d2^{d})$-junta. Let
us briefly explain the various terms involved:

  * •

A function $f$ on the Boolean cube is _Boolean_ if $f(x)\in\\{0,1\\}$ for all
$x\in\\{0,1\\}^{n}$.

  * •

A function $f$ on the Boolean cube has _degree (at most) $d$_ if there is a
polynomial $P$ of degree at most $d$ in $n$ variables such that
$f(x_{1},\ldots,x_{n})=P(x_{1},\ldots,x_{n})$ for all
$x_{1},\ldots,x_{n}\in\\{0,1\\}$.

  * •

A function $f$ is an _$m$ -junta_ if there are $m$ indices $1\leq
i_{1},\ldots,i_{m}\leq n$ and a function $g\colon\\{0,1\\}^{m}\to\mathbb{R}$
such that $f(x_{1},\ldots,x_{n})=g(x_{i_{1}},\ldots,x_{i_{m}})$.

Chiarelli, Hatami and Saks [CHS20] improved the bound to $O(2^{d})$, and the
hidden constant was further optimized by Wellens [Wel20].

The _slice_ $\binom{[n]}{k}$, also known as the _Johnson scheme_ $J(n,k)$,
consists of all vectors in $\\{0,1\\}^{n}$ of Hamming weight $k$. Is it the
case that all Boolean degree $d$ functions on the slice $\binom{[n]}{k}$ are
$m(d)$-juntas, for some constant $m(d)$? Two partial answers to this question
appear in [FI19b, FI19a]. First, if $f$ is a Boolean degree $1$ function on
$\binom{[n]}{k}$ and $k,n-k\geq 2$ then $f$ is a $1$-junta [FI19b]. Second,
there exist constants $C(d)=O(2^{d})$ such that if $f$ is a Boolean degree $d$
function on $\binom{[n]}{k}$ and $k,n-k\geq C(d)$, then $f$ is an
$O(2^{d})$-junta [FI19a].

The reason that both of these results require both $k$ and $n-k$ to be large
is that given a function $f$ on $\binom{[n]}{k}$, we can construct a dual
function $\bar{f}$ on $\binom{[n]}{n-k}$ with similar properties by defining
$\bar{f}(x_{1},\ldots,x_{n})=f(1-x_{1},\ldots,1-x_{n})$. For this reason, when
we consider the slice $\binom{[n]}{k}$, we typically assume that $n\geq 2k$.

One of the open questions in [FI19a] asks for the minimal $k$ for which every
Boolean degree $d$ function on $\binom{[n]}{k}$ is a junta, whenever $n\geq
2k$. In this paper, we completely resolve this question.

######  Theorem 1.1.

Let $d\geq 1$. There exists a constant $m(d)$ such that the following holds.

If $k\geq 2d$ then for any $n\geq 2k$, every Boolean degree $d$ function on
$\binom{[n]}{k}$ is an $m(d)$-junta.

Conversely, if $1\leq k<2d$ then for every $m$ there exist $n\geq 2k$ and a
Boolean degree $d$ function on $\binom{[n]}{k}$ which is not an $m$-junta.

The second part of the theorem follows from functions of the form

$\sum_{i=1}^{\ell}\prod_{j=1}^{e}x_{(e-1)i+j},\quad e=\min(d,k).$

When $n\geq 2\ell e$, these functions are not $\ell e$-juntas.

####  $A$-valued functions

We prove Theorem 1.1 in the more general setting of _$A$ -valued_ functions,
for any finite $A$. These are functions $f$ such that $f(x)\in A$ for all
$x\in\\{0,1\\}^{n}$. When $A=\\{0,1,\ldots,a-1\\}$ (or more generally, any
arithmetic progression of length $a$), the junta threshold is $ad$. The
situation gets more interesting when $A$ is not an arithmetic progression. For
example, when $A=\\{0,1,3\\}$, the threshold for $d=1$ is $k=2$, and the
threshold for $d=2$ is $k=6$. The latter threshold is tight due to the
following example, which is $A$-valued when $k=5$:

$3-2\sum_{1\leq i\leq m}x_{i}+\sum_{1\leq i<j\leq m}x_{i}x_{j}.$

When $A$ is not an arithmetic progression, the threshold depends on a
parameter first studied, in the special case of $A=\\{0,1\\}$, by von zur
Gathen and Roche [vzGR97]. Let $W(A,d)$ be the minimal value $W$ such that
every degree $d$ polynomial $P$ satisfying $P(0),\ldots,P(W)\in A$ is
constant.

######  Theorem 1.2.

Let $A$ be a finite set containing at least two elements, and let $d\geq 1$.
There exists a constant $m(A,d)$ such that the following holds. Define

$k(A,d)=d+\max_{1\leq s\leq
d}\left(\left\lfloor\frac{d}{s}\right\rfloor(W(A,s)-s)\right),$

which is equal to $|A|d$ if $A$ is an arithmetic progression.

If $k\geq k(A,d)$ then for any $n\geq 2k$, every $A$-valued degree $d$
function on $\binom{[n]}{k}$ is an $m(A,d)$-junta.

Conversely, if $1\leq k<k(A,d)$ then for every $m$ there exist $n\geq 2k$ and
an $A$-valued degree $d$ function on $\binom{[n]}{k}$ which is not an
$m$-junta.

When $A$ is an arithmetic progression, the maximum in the definition of
$k(A,d)$ is obtained (not necessarily uniquely) at $s=1$. When $A=\\{0,1,3\\}$
and $d=2$, the maximum is obtained uniquely at $s=2$.

#### The infinite slice

When $1\leq k<2d$, the non-junta example in the Boolean case extends to
_infinitely_ many variables:

$\sum_{i=1}^{\infty}\prod_{j=1}^{e}x_{(e-1)i+j},\quad e=\min(d,k).$

The same holds for the non-junta example we gave for $A=\\{0,1,3\\}$ and
$d=2$. This is a general feature of our non-junta examples. We can think of
such expressions as function on the _infinite slice_ $\binom{[\infty]}{k}$,
which consists of all vectors in $\\{0,1\\}^{\mathbb{N}}$ of Hamming weight
$k$. Conversely, when $k\geq k(A,d)$, every $A$-valued degree $d$ function on
$\binom{[\infty]}{k}$ is a junta.

######  Theorem 1.3.

Let $A$ be a finite set containing at least two elements, and let $d\geq 1$.
The following holds for the parameters $m(A,d),k(A,d)$ defined in Theorem 1.2.

If $k\geq k(A,d)$ then every $A$-valued degree $d$ function on
$\binom{[\infty]}{k}$ is an $m(A,d)$-junta.

Conversely, if $1\leq k<k(A,d)$ then there exists an $A$-valued degree $d$
function on $\binom{[\infty]}{k}$ which is not an $m$-junta for _any_ finite
$m$.

#### Structure of the paper

After a few preliminaries in Section 2, we prove our main theorems in Section
3. We conclude the paper with a few remarks in Section 4.

#### Acknowledgements

This project has received funding from the European Union’s Horizon 2020
research and innovation programme under grant agreement No 802020-ERC-
HARMONIC.

##  2 Preliminaries

#### Slice

For integers $0\leq k\leq n$, we define the _slice_ $\binom{[n]}{k}$ as

$\binom{[n]}{k}=\left\\{x\in\\{0,1\\}^{n}:\sum_{i=1}^{n}x_{i}=k\right\\}.$

We think of functions on the slice as accepting as input $n$ bits
$x_{1},\ldots,x_{n}\in\\{0,1\\}$, with the promise that exactly $k$ of them
are equal to $1$.

A function $f$ on the slice $\binom{[n]}{k}$ is _$A$ -valued_, for some
$A\subseteq\mathbb{R}$, if $f(x)\in A$ for all $x\in\binom{[n]}{k}$. A
_Boolean_ function is an $\\{0,1\\}$-valued function.

#### Degree

For $S\subseteq[n]=\\{1,\ldots,n\\}$, we define

$x_{S}=\prod_{i\in S}x_{i},$

with $x_{\emptyset}=1$. We call $x_{S}$ a _degree $|S|$ monomial_.

A function on the slice $\binom{[n]}{k}$ has _degree (at most) $d$_ if it can
be expressed as a polynomial of degree at most $d$ over the variables
$x_{1},\ldots,x_{n}$. We will usually omit the words “at most”.

######  Lemma 2.1.

If $k\geq d$, then every degree $d$ function on $\binom{[n]}{k}$ can be
expressed as a linear combination of degree $d$ monomials.

###### Proof.

Let $f$ be a degree $d$ function on $\binom{[n]}{k}$. By definition, it can be
expressed as a polynomial $P$ of degree at most $d$. Since $x_{i}^{2}=x_{i}$,
we can replace each monomial of $P$ by its multilinearization, obtained by
replacing higher powers of each $x_{i}$ by $x_{i}$, obtaining a multilinear
polynomial $Q$ of degree at most $d$ expressing $f$. Using the identity

$x_{S}=\frac{1}{\binom{k-|S|}{d-|S|}}\sum_{\begin{subarray}{c}S\subseteq
T\subseteq[n]\\\ |T|=d\end{subarray}}x_{T},$

which is valid over $\binom{[n]}{k}$, we can convert $Q$ into an equivalent
polynomial in which all monomials have degree exactly $d$. ∎

It turns out that if $n-k\geq d$ then the representation given by the lemma is
unique. For this and more on the spectral perspective on functions on the
slice, consult [Fil16, FM19].

#### Junta

A function $f$ on the slice $\binom{[n]}{k}$ is a _$J$ -junta_, where
$J\subseteq[n]$, if there is a function $g\colon\\{0,1\\}^{J}\to\mathbb{R}$
such that $f(x)=g(x|_{J})$ for all $x\in\binom{[n]}{k}$; here $x|_{J}$ is the
restriction of $x$ to the coordinates in $J$.

A function is an _$m$ -junta_ if it is a _$J$ -junta_ for some set $J$ of size
at most $m$.

Given $x\in\binom{[n]}{k}$ and $i,j\in[n]$, we define $x^{(i\;j)}$ to be the
vector obtained by switching coordinates $i$ and $j$.

######  Lemma 2.2.

Let $f$ be a function on the slice $\binom{[n]}{k}$. Suppose that $I,J$ are
disjoint subsets of $[n]$ such that for every $i\in I$ and $j\in J$ there
exists $x\in\binom{[n]}{k}$ such that $f(x)\neq f(x^{(i\;j)})$.

If $f$ is an $m$-junta then $m\geq\min(|I|,|J|)$.

###### Proof.

Suppose that $f$ is an $m$-junta. Then there is a set $K\subseteq[n]$ of size
at most $m$ and a function $g\colon\\{0,1\\}^{K}\to\mathbb{R}$ such that
$f(x)=g(x|_{K})$ for all $x\in\binom{[n]}{k}$. In particular, if $i,j\notin K$
then $f(x)=f(x^{(i\;j)})$ for all $x\in\binom{[n]}{k}$. This shows that either
$K\supseteq I$ or $K\supseteq J$, and so $m\geq|K|\geq\min(|I|,|J|)$. ∎

The main result of [FI19a] states that Boolean degree $d$ functions on
$\binom{[n]}{k}$ are juntas for large $k$.

######  Theorem 2.3 ([FI19a]).

There exist constants $C,K>0$ such that the following holds. If $C^{d}\leq
k\leq n-C^{d}$ and $f$ is a Boolean degree $d$ function on $\binom{[n]}{k}$,
then $f$ is a $KC^{d}$-junta.

A similar result holds for $A$-valued functions.

######  Corollary 2.4.

For every finite set $A$ containing at least two elements there exist
constants $C_{A},K_{A}>0$ such that the following holds. If $C_{A}^{d}\leq
k\leq n-C_{A}^{d}$ and $f$ is an $A$-valued degree $d$ function on
$\binom{[n]}{k}$, then $f$ is a $K_{A}C_{A}^{d}$-junta.

###### Proof.

For each $a\in A$, define

$f_{a}(x)=\prod_{\begin{subarray}{c}b\in A\\\ b\neq
a\end{subarray}}\frac{f(x)-b}{a-b}.$

The function $f_{a}$ is a Boolean degree $(|A|-1)d$ function, and

$f(x)=\sum_{a\in A}af_{a}(x).$

Let $C_{A}=C^{|A|-1}$ and $K_{A}=|A|K$. If $C_{A}^{d}\leq k\leq n-C_{A}^{d}$
then the theorem shows that each $f_{a}$ is a $KC_{A}^{d}$-junta, hence $f$ is
a $K_{A}C_{A}^{d}$-junta. ∎

#### Infinite slice

For an integer $k\geq 0$, we define the _infinite slice_ $\binom{[\infty]}{k}$
as

$\binom{[\infty]}{k}=\left\\{x\in\\{0,1\\}^{\mathbb{N}}:\sum_{i=1}^{\infty}x_{i}=k\right\\}.$

A function $f$ on the infinite slice $\binom{[\infty]}{k}$ has _degree $d$_ if
it can be expressed as an infinite sum of monomials of degree at most $d$:

$f(x)=\sum_{\begin{subarray}{c}S\subseteq\mathbb{N}\\\ |S|\leq
d\end{subarray}}c(S)x_{S}.$

While the sum is infinite, all but $2^{k}$ of the monomials are non-zero on
any given input, and therefore the sum on the right defines a real-valued
function. Lemma 2.1 extends to this setting.

The definition of junta and Lemma 2.2 extend to this setting as well.

#### Bipartite Ramsey theorem

We assume familiarity with the classical Ramsey theorem. Our proof will also
make use of a bipartite Ramsey theorem, whose simple proof we include for
completeness.

######  Theorem 2.5.

Let $c,d\in\mathbb{N}$ be parameters. For every $k\geq 1$ there exists $n\geq
1$ such that the following holds.

Suppose that $A,B$ are two disjoint sets of size $n$. Suppose furthermore that
all subsets of $A\cup B$ of size $d$ are colored using one of $c$ colors. Then
there exist subsets $A^{\prime}\subseteq A$ and $B^{\prime}\subseteq B$ of
size $k$ and colors $c_{0},\ldots,c_{d}$ such that every $T\subseteq
A^{\prime}\cup B^{\prime}$ of size $d$ has color $c_{|T\cap A|}$.

###### Proof.

We will prove the theorem under the assumption that $A,B$ are infinite. The
finite version then follows by compactness.

Let $m$ be such that given a set $X$ of size $m$ together with a coloring of
all of its subsets of size at most $d$ using $c$ colors, we can find a subset
$A^{\prime}\subseteq X$ of size $k$ and colors $c_{0},\ldots,c_{d}$ such that
the color of any $T\subseteq A^{\prime}$ of size at most $d$ is $c_{|T|}$.
Such an $m$ exists due to Ramsey’s theorem.

Let $X$ be an arbitrary subset of $A$ of size $m$. Let $\chi$ be the
$c$-coloring of the subsets of $A\cup B$ of size $d$. Assign every
$T_{B}\subseteq B$ of size at most $d$ the color

$T_{A}\mapsto\chi(T_{A}\cup T_{B}),$

where $T_{A}$ ranges over all subsets of $X$ of size $d-|T_{B}|$. That is, the
color of $T_{B}$ is one of $c^{\binom{m}{d-|T_{B}|}}$ possible functions.
Applying Ramsey’s theorem, we find an infinite subset $B^{\prime}\subseteq B$
and a list of colors $c_{T_{A}}$, one for each $T_{A}\subseteq X$ of size at
most $d$, such that for all $T_{B}\subseteq B^{\prime}$ of size $d-|T_{A}|$,
we have $\chi(T_{A}\cup T_{B})=c_{T_{A}}$.

The choice of $m$ guarantees the existence of a subset $A^{\prime}\subseteq X$
of size $k$ and colors $c_{0},\ldots,c_{d}$ such that for every
$T_{A}\subseteq A^{\prime}$ of size at most $d$ and for every $T_{B}\subseteq
B^{\prime}$ of size $d-|T_{A}|$, we have $\chi(T_{A}\cup
T_{B})=c_{T_{A}}=c_{|T_{A}|}$. ∎

When $A,B$ are infinite, the proof above produces a subset
$A^{\prime}\subseteq A$ of size $k$ and an _infinite_ subset
$B^{\prime}\subseteq B$. It is natural to wonder whether we can ask for both
$A^{\prime}$ and $B^{\prime}$ to be infinite. This is impossible in general.
Indeed, let $A,B$ be two copies of $\mathbb{N}$, and color $A\times B$ using
two colors as follows: $\chi(i,j)=1$ if $i<j$ and $\chi(i,j)=0$ otherwise. The
reader can check that there are no infinite subsets $A^{\prime},B^{\prime}$
such that $\chi(i,j)$ is the same for all $i\in A^{\prime}$ and $j\in
B^{\prime}$.

##  3 Main theorems

In this section we prove Theorems 1.1, 1.2 and 1.3. Since Theorem 1.1 is a
special case of Theorem 1.2, it suffices to prove Theorems 1.2 and 1.3. These
theorems will follow from the following theorem, which is our main result.

######  Theorem 3.1.

Let $A$ be a finite set containing at least two elements, and let $d\geq 1$.
There exists a constant $\kappa(A,d)$, defined below, such that the following
holds.

If $k\geq\kappa(A,d)$ then there exists a constant $m(A,d,k)$ such that every
$A$-valued degree $d$ function on $\binom{[n]}{k}$ is an $m(A,d,k)$-junta.

Conversely, if $1\leq k<\kappa(A,d)$ then for every $m\geq 1$ there exist an
$n$ and an $A$-valued degree $d$ function on $\binom{[n]}{k}$ which is not an
$m$-junta. Similarly, there exists an $A$-valued degree $d$ function on
$\binom{[\infty]}{k}$ which is not an $m$-junta for any finite $m$.

The constant $\kappa(A,d)$ is the smallest value $\kappa$ such that all of the
following hold:

  1. 1.

$\kappa>d$.

  2. 2.

For all $e\in\\{0,\ldots,d-1\\}$: if $P$ is a univariate polynomial of degree
at most $d-e$ and $P(0),\ldots,P(\kappa-e)\in A$ then $P$ is constant.

  3. 3.

For all $t\geq 0$ and $r,s\geq 1$ satisfying $t+rs\leq d$: if $P$ is a
univariate polynomial of degree at most $s$ and
$P(0),\ldots,P(\lfloor\frac{\kappa-t}{r}\rfloor)\in A$ then $P$ is constant.

We show in Section 3.5 that $\kappa(A,d)$ exists, that is, some $\kappa$
satisfies all these constraints.

Since $\kappa\geq d$, if the polynomial $P$ in Item 2 is not constant then the
sequence $P(0),\ldots,P(\kappa-e)$ is not constant. For the same reason, if
the polynomial $P$ in Item 3 is not constant then the sequence
$P(0),\ldots,P(\lfloor\frac{k-t}{r}\rfloor)$ is not constant.

Let us explain this definition by way of proving the converse part of Theorem
3.1.

###### Proof of converse part of Theorem 3.1.

Let $a,b$ be two distinct elements of $A$. For each $k$ such that $1\leq
k<\kappa(A,d)$ and each $m\geq k$, we will construct $n$ and an $A$-valued
degree $d$ function on the slice $\binom{[n]}{k}$ which is not an
$(m-1)$-junta. In order to prove that the function is not a junta, we will
appeal to Lemma 2.2.

Suppose first that $1\leq k\leq d$. Let $n=2km$, and consider the function

$f(x)=a+(b-a)\sum_{i=1}^{m}x_{\\{(i-1)k+1,\ldots,ik\\}}.$

By construction, $f$ has degree at most $k$. The sum is always at most $1$,
and so this function is $A$-valued. Let $I=\\{1,\ldots,km\\}$ and
$J=\\{km+1,\ldots,2km\\}$. For each $i^{\prime}=(i-1)k+\ell\in I$ and $j\in
J$, let $x\in\binom{[n]}{k}$ be given by $x_{(i-1)k+1}=\cdots=x_{ik}=1$, and
all other coordinates are zero. Then $f(x)=b$ and $f(x^{(i^{\prime}\;j)})=a$.
Applying Lemma 2.2, we see that $f$ is not an $(m-1)$-junta.

From now on, we assume that $k>d$.

Suppose next that $e\in\\{0,\ldots,d-1\\}$ and there exists a univariate
polynomial $P$ of degree at most $d-e$ such that $P(0),\ldots,P(k-e)\in A$ and
$P$ is non-constant. Since $k\geq d$, the list $P(0),\ldots,P(k-e)$ cannot be
constant, and so $P(w)\neq P(w-1)$ for some $w\in\\{1,\ldots,k-e\\}$. Let
$n=e+2m$, where $m\geq k-e$, and consider the function

$f(x)=a(1-x_{\\{1,\ldots,e\\}})+x_{\\{1,\ldots,e\\}}P\left(\sum_{i=1}^{m}x_{e+i}\right).$

By construction, $f$ has degree at most $e+(d-e)=d$. If
$x_{\\{1,\ldots,e\\}}=0$ then $f(x)=a$, and otherwise, the input to $P$ is at
most $k-e$, and so $f$ is $A$-valued. Let $I=\\{e+1,\ldots,e+m\\}$ and
$J=\\{e+m+1,\ldots,e+2m\\}$. For each $i^{\prime}=i+e\in I$ and $j\in J$, let
$x\in\binom{[n]}{k}$ be any input such that $x_{1}=\cdots=x_{e}=1$;
$x_{e+h}=1$ for exactly $w$ many $h\in\\{1,\ldots,m\\}$; and $x_{j}=0$. This
requires $e+w\leq k$ inputs to be $1$ and $m-w+1\leq m$ inputs to be $0$.
Since $n-k\geq m$, such an input exists. The input $x$ satisfies $f(x)=P(w)$
and $f(x^{(i\;j)})=P(w-1)$. Applying Lemma 2.2, we see that $f$ is not an
$(m-1)$-junta.

Finally, suppose that $t\geq 0$ and $r,s\geq 1$ satisfy $t+rs\leq d$, and that
there exists a univariate polynomial $P$ of degree at most
$s\leq\lfloor\frac{d-t}{r}\rfloor$ such that
$P(0),\ldots,P(\lfloor\frac{k-t}{r}\rfloor)\in A$ and $P$ is non-constant.
Since $k\geq d$, the list $P(0),\ldots,P(\lfloor\frac{k-t}{r}\rfloor)$ cannot
be constant, and so $P(w)\neq P(w-1)$ for some
$w\in\\{1,\ldots,\lfloor\frac{k-t}{r}\rfloor\\}$. Let $n=t+2rm$, where $m\geq
k-t$, and consider the function

$f(x)=a(1-x_{\\{1,\ldots,t\\}})+x_{\\{1,\ldots,t\\}}P\left(\sum_{i=1}^{m}x_{\\{t+(i-1)r+1,\ldots,t+ir\\}}\right).$

By construction, $f$ has degree at most $t+rs\leq d$. If
$x_{\\{1,\ldots,t\\}}=0$ then $f(x)=a$, and otherwise, the input to $P$ is at
most $\frac{k-t}{r}$, and so $f$ is $A$-valued. Let $I=\\{t+1,\ldots,t+rm\\}$
and $J=\\{t+rm+1,\ldots,t+2rm\\}$. For each $i^{\prime}=t+(i-1)r+\ell$ and
$j\in J$, let $x\in\binom{[n]}{k}$ be given by $x_{1}=\cdots=x_{t}=1$;
$x_{t+(h-1)r+1}=\cdots=x_{t+hr}=1$ for exactly $w$ many
$h\in\\{1,\ldots,m\\}$; and $x_{j}=0$. This requires $t+rw\leq k$ inputs to be
$1$ and $m-w+1\leq m$ inputs to be $0$. Since $n-k\geq m$, such an input
exists. The input $x$ satisfies $f(x)=P(w)$ and $f(x^{(i\;j)})=P(w-1)$.
Applying Lemma 2.2, we see that $f$ is not an $(m-1)$-junta.

Taking $m=\infty$ and allowing for infinitely many more input coordinates, in
all cases listed above we obtain $A$-valued degree $d$ functions on
$\binom{[\infty]}{k}$ which are not $m$-juntas for any finite $m$. For
example, when $1\leq k\leq d$ we can consider the function

$f(x)=a+(b-a)\sum_{i=1}^{\infty}x_{\\{2(i-1)k+2,\ldots,2ik\\}}.$

For any $m$, we can take $I=\\{x_{2},x_{4},\ldots,x_{2m}\\}$ and
$J=\\{x_{1},x_{3},\ldots,x_{2m-1}\\}$ and conclude, via Lemma 2.2, that $f$ is
not an $(m-1)$-junta. ∎

The proof of Theorem 3.1 occupies Sections 3.1, 3.2, 3.3 and 3.4. In order to
complete the proof of Theorems 1.2 and 1.3, we need the following lemma,
proved in Section 3.4.

######  Lemma 3.2.

Let $A$ be a finite set containing at least two elements, and let $d\geq 1$.
The parameters $\kappa(A,d)$ and $k(A,d)$, defined in Theorems 3.1 and 1.2,
are equal.

Furthermore, if $A$ is an arithmetic progression then $k(A,d)=|A|d$.

We can now prove our main theorems.

###### Proof of Theorem 1.2.

Given Lemma 3.2, the converse direction follows from Theorem 3.1. These two
results also imply that for every $k\geq k(A,d)$ there is a constant
$m(A,d,k)$ such that for any $n\geq 2k$, any $A$-valued degree $d$ function on
$\binom{[n]}{k}$ is an $m(A,d,k)$-junta. Corollary 2.4 shows that if $k\geq
C_{A}^{d}$, $n\geq 2k$, and $f$ is an $A$-valued degree $d$ function on
$\binom{[n]}{k}$, then $f$ is a $K_{A}C_{A}^{d}$-junta. Therefore the theorem
holds for

$m(A,d)=\max(m(A,d,k(A,d)),\ldots,m(A,d,C_{A}^{d}),K_{A}C_{A}^{d}).\qed$

###### Proof of Theorem 1.3.

Given Lemma 3.2, the converse direction follows from Theorem 3.1. Suppose now
that $k\geq k(A,d)$ and that $f$ is an $A$-valued degree $d$ function on
$\binom{[\infty]}{k}$.

We first show that $f$ is an $m$-junta for $m=2m(A,d)$. Suppose that this is
not the case. We construct a sequence
$i_{1},j_{1},\ldots,i_{m(A,d)+1},j_{m(A,d)+1}$ as follows. Given
$i_{1},j_{1},\ldots,i_{t},j_{t}$ for $t\leq m(A,d)$, since $f$ is not a
$K_{t}$-junta for $K_{t}=\\{i_{1},j_{1},\ldots,i_{t},j_{t}\\}$, we can find an
input $v_{t+1}\in\binom{[\infty]}{k}$ and indices $i_{t+1},j_{t+1}\notin
K_{t}$ such that $f(v_{t+1})\neq f(v_{t+1}^{(i_{t+1}\;j_{t+1})})$.

Let $S_{t}$ be the set of $1$-indices of $v_{t}$, and let $f^{\prime}$ be the
restriction of $f$ to a finite slice obtained by zeroing out all coordinates
other than the ones in

$\bigcup_{t=1}^{m(A,d)+1}(S_{t}\cup\\{i_{t},j_{t}\\}).$

According to Theorem 1.2, $f^{\prime}$ is a $K$-junta for some $K$ of size at
most $m(A,d)$. By construction, the inputs $v_{1},\ldots,v_{m(A,d)+1}$
restrict to inputs on the domain of $f^{\prime}$ which satisfy
$f^{\prime}(v_{t})\neq f^{\prime}(v_{t}^{(i_{t}\;j_{t})})$. This means that
$K$ intersects $\\{i_{t},j_{t}\\}$ for all $t\in[m(A,d)+1]$, and so
$|K|>m(A,d)$. This contradiction shows that $f$ must be an $m$-junta.
Therefore we can identify $f$ with an $A$-valued degree $d$ function on
$\binom{[m]}{d}$, which according to Theorem 1.2 is an $m(A,d)$-junta. ∎

###  3.1 Quantization

Let $f$ be an $A$-valued degree $d$ function on $\binom{[n]}{k}$, where $k\geq
d$. According to Lemma 2.1, we can represent $f$ as a linear combination of
degree $d$ monomials. In this part of the proof we show that the coefficients
are _quantized_ , in the sense that they belong to a set $\mathfrak{C}$
depending only on $A,d,k$.

######  Lemma 3.3.

For any $k\geq d\geq 1$ and finite $A\subseteq\mathbb{R}$ there exists a
finite set $\mathfrak{C}\subseteq\mathbb{R}$ such that the following holds.

Let $f$ be an $A$-valued degree $d$ function on $\binom{[n]}{k}$, where $n\geq
k+d$, and suppose that

$f(x)=\sum_{\begin{subarray}{c}S\subseteq[n]\\\
|S|=d\end{subarray}}c(S)x_{S}.$

Then all coefficients $c(S)$ belong to $\mathfrak{C}$.

###### Proof.

Let $S\subseteq[n]$ be an arbitrary subset of size $d$, and let
$I\subseteq[n]$ be an arbitrary subset of size $k$ disjoint from $S$. For
every $e\in\\{0,\ldots,d\\}$, define

$h(e)=\sum_{\begin{subarray}{c}S^{\prime}\subseteq S\\\
|S^{\prime}|=e\end{subarray}}\sum_{\begin{subarray}{c}I^{\prime}\subseteq I\\\
|I^{\prime}|=k-e\end{subarray}}f(S^{\prime}\cup I^{\prime}).$

Each $h(e)$ is a sum of at most $2^{d+k}$ many elements from $A$, and so
belongs to some finite set.

In order to express $h(e)$ in terms of coefficients $c(T)$, for
$e\in\\{0,\ldots,d\\}$ define

$\gamma(e)=\sum_{\begin{subarray}{c}S^{\prime}\subseteq S\\\
|S^{\prime}|=e\end{subarray}}\sum_{\begin{subarray}{c}I^{\prime}\subseteq I\\\
|I^{\prime}|=d-e\end{subarray}}c(S^{\prime}\cup I^{\prime}).$

Simple combinatorics shows that

$h(e)=\sum_{e^{\prime}=0}^{e}\binom{e}{e^{\prime}}\binom{k-e}{d-e}\gamma(e^{\prime}).$

Each $h(e)$ is a linear combination of $\gamma(0),\ldots,\gamma(e)$ whose
coefficients depend only on $d,k$, in which the coefficient of $\gamma(e)$ is
non-zero. Therefore we can express each $\gamma(e)$ as a similar linear
combination of $h(0),\ldots,h(e)$. In particular, $c(S)=\gamma(d)$ is some
linear combination of $h(0),\ldots,h(d)$, and so belongs to some finite set. ∎

The condition $n-k\geq d$ is necessary: if $n-k<d$ then

$C\prod_{i=1}^{d}(1-x_{i})$

is a degree $d$ polynomial which represents the zero function for any
$C\in\mathbb{R}$.

As an aside, Lemma 3.3 implies that the representation of Lemma 2.1 is unique.
Indeed, if $f=\sum_{S}c_{1}(S)x_{S}=\sum_{S}c_{2}(S)x_{S}$ are two such
representations, then $f=\sum_{S}(\theta c_{1}(S)+(1-\theta)c_{2}(S))x_{S}$ in
another such representation for any real $\theta$. If $c_{1}(S)\neq c_{2}(S)$,
then $\\{\theta
c_{1}(S)+(1-\theta)c_{2}(S):\theta\in\mathbb{R}\\}=\mathbb{R}$, contradicting
Lemma 3.3 when applied to the finite set $A$ which is the range of $f$.

###  3.2 Bunching of coefficients

Suppose that $f$ is a degree $d$ junta. Lemma 3.3 shows that its degree $d$
expansion is quantized. Yet it is not necessarily the case that the degree $d$
expansion is sparse. For example, the degree $d$ expansion of
$x_{\\{1,\ldots,d-1\\}}$ is

$\frac{1}{k-d+1}\sum_{i=d}^{n}x_{\\{1,\ldots,d-1,i\\}}.$

In the following steps of the proof, we gradually convert this kind of
expansion into an expansion which mentions a bounded number of variables. The
first step shows that the coefficients $c(S)$ in the degree $d$ expansion are
“bunched” in the following sense.

######  Lemma 3.4.

For finite $A\subseteq\mathbb{R}$ containing at least two elements, $d\geq 1$,
and $k\geq\kappa(A,d)$, there is a constant $N$ for which the following holds.

Let $f$ be an $A$-valued degree $d$ function on $\binom{[n]}{k}$, where $n\geq
k+d$, and suppose that

$f(x)=\sum_{\begin{subarray}{c}S\subseteq[n]\\\ |S|=d\end{subarray}}c(S)x_{S}$

is the expansion whose existence is guaranteed by Lemma 2.1.

We can assign each subset $T\subseteq[n]$ of size smaller than $d$ a value
$c(T)\in\mathfrak{C}$ (where $\mathfrak{C}$ is the set promised by Lemma 3.3)
such that $c(T\cup\\{i\\})=c(T)$ for all but $N$ many $i\in[n]\setminus T$.

The proof of Lemma 3.4 proceeds by backwards induction on the size of the set
$T$. The bulk of the work lies in the basis of the induction.

###### Proof of Lemma 3.4, base case.

Under the assumptions of Lemma 3.4, we assign for each subset $T\subseteq[n]$
of size $d-1$ a value $c(T)\in\mathfrak{C}$ such that $c(T\cup\\{i\\})=c(T)$
for all but $N_{d-1}$ many $i\in[n]\setminus T$, where $N_{d-1}$ is a constant
depending only on $A,d,k$.

Fix a subset $T\subseteq[n]$ of size $d-1$. We partition $[n]\setminus T$ into
$|\mathfrak{C}|$ sets $X_{\gamma}$ as follows: $X_{\gamma}$ contains all
$i\notin T$ such that $c(T\cup\\{i\\})=\gamma$. For every
$\gamma_{1}\neq\gamma_{2}$, we color all non-empty subsets $S\subseteq
X_{\gamma_{1}}\cup X_{\gamma_{2}}$ of size at most $d$ as follows: the color
assigned to $S$ is

$T^{\prime}\mapsto c(T^{\prime}\cup S),$

where $T^{\prime}$ ranges over all subsets of $T$ of size $d-|S|$. According
to Lemma 3.3, the color of $S$ is one of $|\mathfrak{C}|^{\binom{d-1}{d-|S|}}$
possible functions. Applying Theorem 2.5 repeatedly, there is a constant $M$,
depending only on $A,d,k$, such that if $|X_{\gamma_{1}}|,|X_{\gamma_{2}}|\geq
M$ then there exist subsets $X^{\prime}_{\gamma_{1}}\subseteq X_{\gamma_{1}}$
and $X^{\prime}_{\gamma_{2}}\subseteq X_{\gamma_{2}}$ of size $k$ and colors
$c_{T^{\prime},e}\in\mathfrak{C}$, for all $T^{\prime}\subseteq T$ and $e\leq
d-|T^{\prime}|$, such that if $S\subseteq T\cup X^{\prime}_{\gamma_{1}}\cup
X^{\prime}_{\gamma_{2}}$ has size $d$ then $c(S)=c_{S\cap T,S\cap
X_{\gamma_{1}}}$.

We now prove that for every $T^{\prime}\subseteq T$ there exists a color
$c_{T^{\prime}}\in\mathfrak{C}$ such that $c_{T^{\prime},e}=c_{T^{\prime}}$
for all $e\leq d-|T^{\prime}|$. The proof is by induction on $|T^{\prime}|$.
Suppose that the claim holds for all proper subsets of some
$T^{\prime}\subseteq T$. We prove it for $T^{\prime}$.

Let $w\leq k-|T^{\prime}|$. The value of $f$ on an input consisting of
$T^{\prime}$ together with $w$ elements from $X^{\prime}_{\gamma_{1}}$ and
$k-|T^{\prime}|-w$ elements from $X^{\prime}_{\gamma_{2}}$ is

$\sum_{T^{\prime\prime}\subsetneq
T^{\prime}}\binom{k-|T^{\prime\prime}|}{d-|T^{\prime\prime}|}c_{T^{\prime\prime}}+\sum_{e=0}^{d-|T^{\prime}|}\binom{w}{e}\binom{k-|T^{\prime}|-w}{d-|T^{\prime}|-e}c_{T^{\prime},e}.$

This is a polynomial $P(w)$ of degree at most $d-|T^{\prime}|$ such that
$P(0),\ldots,P(k-|T^{\prime}|)\in A$, and so since $k\geq\kappa(A,d)$, $P$ is
constant.

Since $P(e)$ only depends on $c_{T^{\prime},0},\ldots,c_{T^{\prime},e}$, it
follows that for every $w\in\\{1,\ldots,d-|T^{\prime}|\\}$ we have

$P(w)-P(w-1)=\binom{k-|T^{\prime}|-w}{d-|T^{\prime}|-w}c_{T^{\prime},w}-\sum_{e=0}^{w-1}\rho_{w,e}c_{T^{\prime},e},$

for some $\rho_{w,0},\ldots,\rho_{w,w-1}$. If
$c_{T^{\prime},0}=c_{T^{\prime},1}=\cdots=c_{T^{\prime},w}=c_{T^{\prime}}$
then $P(w)=P(w-1)$ since both are equal to $\sum_{T^{\prime\prime}\subseteq
T^{\prime}}\binom{k-|T^{\prime\prime}|}{d-|T^{\prime\prime}|}c_{T^{\prime\prime}}$.
This shows that
$\sum_{e}\rho_{w,e}=\binom{k-|T^{\prime}|-w}{d-|T^{\prime}|-w}$.

We can now prove inductively that $c_{T^{\prime},w}=c_{T^{\prime},0}$ for
$w\in\\{1,\ldots,d-|T^{\prime}|\\}$. Suppose that this holds for
$w^{\prime}<w$. Then
$0=P(w)-P(w-1)=\binom{k-|T^{\prime}|-w}{d-|T^{\prime}|-w}(c_{T^{\prime},w}-c_{T^{\prime},0})$,
and so $c_{T^{\prime},w}=c_{T^{\prime},0}$. We can therefore take
$c_{T^{\prime}}=c_{T^{\prime},0}$.

Any $i_{1}\in X^{\prime}_{\gamma_{1}}$ satisfies
$\gamma_{1}=c(T\cup\\{i_{1}\\})=c_{T,1}$. Similarly, any $i_{2}\in
X^{\prime}_{\gamma_{2}}$ satisfies $\gamma_{2}=c(T\cup\\{i_{2}\\})=c_{T,0}$.
Since $\gamma_{1}\neq\gamma_{2}$ whereas $c_{T,0}=c_{T,1}$, we reach a
contradiction. It follows that at most one of the sets $X_{\gamma}$ can
satisfy $|X_{\gamma}|\geq M$. Choosing $c(T^{\prime})$ to be the value
$\gamma$ which maximizes $|X_{\gamma}|$, the base case follows, with
$N_{d-1}=|\mathfrak{C}|M$. ∎

The inductive step is more elementary.

###### Proof of Lemma 3.4, inductive step.

Let $e\leq d-2$. Suppose that each subset $T\subseteq[n]$ of size $e+1$ is
assigned a value $c(T)\in\mathfrak{C}$ such that $c(T\cup\\{i\\})=c(T)$ for
all but $N_{e+1}$ many $i\in[n]\setminus T$. We assign for each subset
$T\subseteq[n]$ of size $e$ a value $c(T)\in\mathfrak{C}$ such that
$c(T\cup\\{i\\})=c(T)$ for all but $N_{e}$ many $i\in[n]\setminus T$, where
$N_{e}=|\mathfrak{C}|(N_{e+1}^{2}+N_{e+1}+1)$.

Fix a subset $T\subseteq[n]$ of size $e$. For $\gamma\in\mathfrak{C}$, let
$X_{\gamma}$ consist of all $i\in[n]\setminus T$ such that
$c(T\cup\\{i\\})=\gamma$. In order to prove the inductive step, it suffices to
show that at most one $\gamma\in\mathfrak{C}$ satisfies $|X_{\gamma}|\geq
N_{e+1}^{2}+N_{e+1}+1$.

Suppose, for the sake of contradiction, that
$|X_{\gamma_{1}}|,|X_{\gamma_{2}}|\geq N_{e+1}^{2}+N_{e+1}+1$ for some
$\gamma_{1}\neq\gamma_{2}$. Choose $N_{e+1}+1$ arbitrary elements
$i_{1},\ldots,i_{N_{e+1}+1}\in X_{\gamma_{1}}$. By assumption, for each
$i_{s}$ there is an exceptional set $E_{s}$ of size at most $N_{e+1}$ such
that if $j\in[n]\setminus(T\cup\\{i_{s}\\}\cup E_{s})$ then
$c(T\cup\\{i_{s},j\\})=c(T\cup\\{i_{s}\\})=\gamma_{1}$. Since
$|X_{\gamma_{2}}|>(N_{e+1}+1)N_{e+1}$, there exists $j\in X_{\gamma_{2}}$
which does not belong to any $E_{s}$, and consequently
$c(T\cup\\{j,i_{s}\\})=\gamma_{1}$ for all $s\in\\{1,\ldots,N_{e+1}+1\\}$.
However, this contradicts the promise that
$c(T\cup\\{j,i\\})=c(T\cup\\{j\\})=\gamma_{2}$ for all but $N_{e+1}$ many
$i\in[n]\setminus(T\cup\\{j\\})$. ∎

Lemma 3.4 follows by taking $N=\max(N_{0},\ldots,N_{d-1})$.

###  3.3 Sparsification

If $c(S)\neq 0$ for some $S$ of size $d-1$, then we can sparsify the expansion
of $f$ by introducing the appropriate product of $x_{S}$. In this way, we can
recover $x_{\\{1,\ldots,d-1\\}}$ from its degree $d$ expansion. The following
lemma carries out this procedure for all sets of size smaller than $d$.

######  Lemma 3.5.

For finite $A\subseteq\mathbb{R}$ containing at least two elements, $d\geq 1$,
and $k\geq\kappa(A,d)$, there is a constant $M$ and a finite subset
$\mathfrak{D}$ for which the following holds.

Let $f$ be an $A$-valued degree $d$ function on $\binom{[n]}{k}$, where $n\geq
k+d$. Then $f$ has an expression of the form

$f(x)=\sum_{\begin{subarray}{c}S\subseteq[n]\\\ |S|\leq
d\end{subarray}}C(S)x_{S},$

where $C(S)\in\mathfrak{D}$, and for every $T\subseteq[n]$ of size less than
$d$, we have $C(T\cup\\{i\\})=0$ for all but at most $M$ many
$i\in[n]\setminus T$.

###### Proof.

The transformation proceeds in several stages, and accordingly, for each
$e\leq d$ we will construct a constant $M_{e}$, a finite subset
$\mathfrak{D}_{e}$ (both depending only on $A,d,k$), and coefficients
$c_{e}(S)\in\mathfrak{D}_{e}$ for all sets $S\subseteq[n]$ of size at most
$d$, such that

$f(x)=\sum_{\begin{subarray}{c}S\subseteq[n]\\\ |S|<e\text{ or
}|S|=d\end{subarray}}\binom{k-|S|}{d-|S|}c_{e}(S)x_{S}$

and the following properties hold:

  1. (a)

For every $T\subseteq[n]$ of size less than $e$, we have
$c_{e}(T\cup\\{i\\})=0$ for all but at most $M_{e}$ many $i\in[n]\setminus T$.

  2. (b)

For every $T\subseteq[n]$ of size between $e$ and $d-1$, we have
$c_{e}(T\cup\\{i\\})=c_{e}(T)$ for all but at most $M_{e}$ many
$i\in[n]\setminus T$.

Once we prove that, taking $M=M_{d}$, $\mathfrak{D}=\mathfrak{D}_{d}$ and
$C(S)=\binom{k-|S|}{d-|S|}c_{d}(S)$ will prove the lemma.

When $e=0$, Lemma 3.4 shows that we can take $M_{0}=N$,
$\mathfrak{D}_{0}=\mathfrak{C}$, and $c_{0}=c$.

Now suppose that we have constructed $M_{e},\mathfrak{D}_{e},c_{e}$, where
$e<d$. We define $c_{e+1}(S)=c_{e}(S)$ if $|S|\leq e$, and

$c_{e+1}(S)=c_{e}(S)-\sum_{\begin{subarray}{c}T\subseteq S\\\
|T|=e\end{subarray}}c_{e}(T)$

if $|S|>e$. Since the sum on the right contains at most $2^{d}$ terms, we can
construct the finite subset $\mathfrak{D}_{e+1}$ from the finite subset
$\mathfrak{D}_{e}$. Next, let us check that the new coefficients represent
$f$:

$\sum_{\begin{subarray}{c}S\subseteq[n]\\\ |S|\leq e\text{ or
}|S|=d\end{subarray}}\binom{k-|S|}{d-|S|}c_{e+1}(S)x_{S}=\\\
\sum_{\begin{subarray}{c}S\subseteq[n]\\\
|S|<e\end{subarray}}\binom{k-|S|}{d-|S|}c_{e}(S)x_{S}+\sum_{\begin{subarray}{c}T\subseteq[n]\\\
|T|=e\end{subarray}}\binom{k-e}{d-e}c_{e}(T)x_{T}+\sum_{\begin{subarray}{c}S\subseteq[n]\\\
|S|=d\end{subarray}}\left(c_{e}(S)-\sum_{\begin{subarray}{c}T\subseteq S\\\
|T|=e\end{subarray}}c_{e}(T)\right)x_{S}=\\\
\sum_{\begin{subarray}{c}S\subseteq[n]\\\
|S|<e\end{subarray}}\binom{k-|S|}{d-|S|}c_{e}(S)x_{S}+\sum_{\begin{subarray}{c}T\subseteq[n]\\\
|T|=e\end{subarray}}c_{e}(T)\sum_{\begin{subarray}{c}T\subseteq
S\subseteq[n]\\\
|S|=d\end{subarray}}x_{S}+\sum_{\begin{subarray}{c}S\subseteq[n]\\\
|S|=d\end{subarray}}\left(c_{e}(S)-\sum_{\begin{subarray}{c}T\subseteq S\\\
|T|=e\end{subarray}}c_{e}(T)\right)x_{S}=\\\
\sum_{\begin{subarray}{c}S\subseteq[n]\\\
|S|<e\end{subarray}}\binom{k-|S|}{d-|S|}c_{e}(S)x_{S}+\sum_{\begin{subarray}{c}S\subseteq[n]\\\
|S|=d\end{subarray}}c_{e}(S)x_{S}=f(x).$

It remains to prove properties (a) and (b). Property (a) follows for sets of
size less than $e$ by induction. If $T\subseteq[n]$ has size $e$ and
$c_{e+1}(T\cup\\{i\\})\neq 0$ for some $i\in[n]\setminus T$ then since

$c_{e+1}(T\cup\\{i\\})=c_{e}(T\cup\\{i\\})-c_{e}(T)-\sum_{\begin{subarray}{c}R\subseteq
T\\\ |R|=e-1\end{subarray}}c_{e}(R\cup\\{i\\}),$

either $c_{e}(T\cup\\{i\\})\neq c_{e}(T)$ or $c_{e}(R\cup\\{i\\})\neq 0$ for
some subset $R\subseteq T$ of size $e-1$. Property (b) of $c_{e}$ shows that
there are at most $M_{e}$ many $i\notin T$ such that $c_{e}(T\cup\\{i\\})\neq
c_{e}(T)$. For each $R$, property (a) of $c_{e}$ shows that there are at most
$M_{e}$ many $i\notin T$ such that $c_{e}(R\cup\\{i\\})\neq 0$. In total, we
deduce that $c_{e+1}(T\cup\\{i\\})=0$ for all but at most $(e+1)M_{e}$ indices
$i\notin T$.

The proof of property (b) is similar. If $T\subseteq[n]$ has size at least
$e+1$ and $c_{e+1}(T\cup\\{i\\})\neq c_{e+1}(T)$ then since

$c_{e+1}(T\cup\\{i\\})-c_{e+1}(T)=c_{e}(T\cup\\{i\\})-c_{e}(T)+\sum_{\begin{subarray}{c}R\subseteq
T\\\ |R|=e-1\end{subarray}}c_{e}(R\cup\\{i\\}),$

either $c_{e}(T\cup\\{i\\})\neq c_{e}(T)$ or $c_{e}(R\cup\\{i\\})\neq 0$ for
some $R\subseteq T$ of size $e-1$ not including $i$. Property (b) of $c_{e}$
shows that there are at most $M_{e}$ many $i\notin T$ such that
$c_{e}(T\cup\\{i\\})\neq c_{e}(T)$. For each $R$, property (a) of $c_{e}$
shows that there are at most $M_{e}$ many $i\notin T$ such that
$c_{e}(R\cup\\{i\\})\neq 0$. In total, we deduce that
$c_{e+1}(T\cup\\{i\\})=c_{e+1}(T)$ for all but at most $2^{d}M_{e}$ indices
$i\notin T$.

We complete the proof of the inductive step by taking $M_{e+1}=2^{d}M_{e}$. ∎

###  3.4 Junta conclusion

Lemma 3.5 gives us an expression for $f$ in which the coefficients $C(S)$ are
locally sparse: for each $T$, only a bounded number of coefficients
$C(T\cup\\{i\\})$ are non-zero. We would like to extend this to global
sparsity: only a bounded number of coefficients $C(S)$ are non-zero. We do so
in steps, proving the following lemma inductively.

######  Lemma 3.6.

For any finite $A\subseteq\mathbb{R}$ containing at least two elements, $d\geq
1$, and $k\geq\kappa(A,d)$, and any $t+r\leq d$, there exist constants
$N(t,r)\geq k+d$ and $L(t,r)$ such that the following holds.

Let $f$ be an $A$-valued degree $d$ function on $\binom{[n]}{k}$, where $n\geq
N(t,r)$. Let $C(S)$ be the coefficients of the expression in Lemma 3.5. For
any subset $T\subseteq[n]$ of size $t$, there at most $L(t,r)$ many subsets
$R\subseteq[n]\setminus T$ of size $r$ such that $C(T\cup R)\neq 0$.

Before proving the lemma, let us briefly show how it implies the main part of
Theorem 3.1 (we proved the converse part at the beginning of Section 3).

###### Proof of main part of Theorem 3.1.

We prove the theorem with

$m(A,d,k)=\max\left(N(0,1),\ldots,N(0,d),\sum_{r=1}^{d}rL(0,r)\right).$

Let $f$ be an $A$-valued degree $d$ function on $\binom{[n]}{k}$, where
$k\geq\kappa(A,d)$. If $n<N(0,r)$ for some $r\in\\{1,\ldots,d\\}$, then $f$ is
trivially an $n$-junta, and so an $m(A,d,k)$-junta. Otherwise, consider the
expression promised by Lemma 3.5:

$f(x)=\sum_{\begin{subarray}{c}S\subseteq[n]\\\ |S|\leq
d\end{subarray}}C(S)x_{S}.$

According to Lemma 3.6, for all $r\in\\{1,\ldots,d\\}$, at most $L(0,r)$ many
sets $S\subseteq[n]$ of size $r$ satisfy $C(S)\neq 0$. If we take the union of
all these sets for all $r$, we obtain a set $J$ of size at most $m(A,d,k)$
such that $f$ is a $J$-junta, completing the proof. ∎

We now turn to the proof of Lemma 3.6.

###### Proof of Lemma 3.6.

When $r=0$, the lemma trivially holds, for $N(t,0)=k+d$ and $L(t,0)=1$. When
$r=1$, the lemma follows directly from Lemma 3.5, taking $N(t,1)=k+d$ and
$L(t,1)=M$. Therefore we can assume that $r\geq 2$.

We prove the lemma for all other parameters by induction: first on $r$, then
on $t$. This means that given $t,r$, we assume that the lemma holds for all
$(t^{\prime},r^{\prime})$ such that $r^{\prime}<r$ and for all
$(t^{\prime},r)$ such that $t^{\prime}<t$, and prove it for $(t,r)$.

Let us be given $t,r$ such that $t+r\leq d$ and $r\geq 2$, and let
$T\subseteq[n]$ be a set of size $t$. We want to bound the size of the
collection $\mathcal{R}$ consisting of all subsets of $[n]$ of size $r$ which
are disjoint from $T$ and satisfy $C(T\cup R)\neq 0$. We will show that for
the correct choice of $N(t,r)\geq t+r$ and $L(t,r)$, the assumption
$|\mathcal{R}|\geq L(t,r)$ leads to a contradiction. It follows that
$|\mathcal{R}|<L(t,r)$.

Starting with $\mathcal{R}$, we will extract subcollections
$\mathcal{R}\supseteq\mathcal{R}_{1}\supseteq\mathcal{R}_{2}\supseteq\mathcal{R}_{3}\supseteq\mathcal{R}_{4}$
which are more and more structured:

  * •

All $R\in\mathcal{R}_{1}$ are _good_ : $C(S)=0$ for all subsets $S\subseteq
T\cup R$ intersecting $R$ other than $T\cup R$ itself.

  * •

The sets in $\mathcal{R}_{2}$ are disjoint.

  * •

If $R_{1},\ldots,R_{s}\in\mathcal{R}_{3}$ are such that $C(S)\neq 0$ for some
subset $S\subseteq T\cup R_{1}\cup\cdots\cup R_{s}$ intersecting
$R_{1},\ldots,R_{s}$ and different from $T\cup R_{i}$ then $|S\cap T|+rs\leq
d$.

  * •

For all $T^{\prime}\subseteq T$ and all
$R_{1},\ldots,R_{s}\in\mathcal{R}_{4}$, the sum of $C(T^{\prime}\cup S)$ over
all subsets $S\subseteq R_{1}\cup\cdots\cup R_{s}$ intersecting
$R_{1},\ldots,R_{s}$ only depends on $T^{\prime}$ and $s$.

Choosing $L(t,r)$ large enough, we will be able to guarantee that
$|\mathcal{R}_{4}|\geq k$. Choosing $N(t,r)$ large enough, we will be able to
find $k$ many points $P$ outside of $T,\mathcal{R}_{4}$ such that $C(S)=0$ for
any $S\subseteq T\cup\bigcup\mathcal{R}_{4}\cup P$ intersecting $P$, and this
will enable us to reach a contradiction.

We now proceed with the details. Rephrasing the above definition, a set
$R\in\mathcal{R}$ is good if $C(T^{\prime}\cup R^{\prime})=0$ for all
$T^{\prime}\subseteq T$ and non-empty $R^{\prime}\subseteq R$, other than
$T^{\prime}=T$ and $R^{\prime}=R$. In order to show that many sets are good,
we bound the number of sets which are bad.

Let $T^{\prime}\subsetneq T$ be a set of size $t^{\prime}<t$. According to the
induction hypothesis, the number of $R^{\prime}\subseteq[n]$ of size
$r^{\prime}\in\\{1,\ldots,r\\}$ disjoint from $T^{\prime}$ such that
$C(T^{\prime}\cup R^{\prime})\neq 0$ is at most $L(t^{\prime},r^{\prime})$.
Applying the induction hypothesis again, for each such $R^{\prime}$, the
number of sets $R^{\prime\prime}\subseteq[n]$ of size $r-r^{\prime}$ disjoint
from $T^{\prime}\cup R^{\prime}$ such that $C(T^{\prime}\cup R^{\prime}\cup
R^{\prime\prime})\neq 0$ is at most $L(t^{\prime}+r^{\prime},r-r^{\prime})$.
Every set $R\in\mathcal{R}$ which is bad due to $T^{\prime}\neq T$ is of the
form $R^{\prime}\cup R^{\prime\prime}$, and so for each $T^{\prime}$, there
are at most $L(t^{\prime},r^{\prime})L(t^{\prime}+r^{\prime},r-r^{\prime})$
such sets.

If $T^{\prime}=T$ then the same argument works as long as $r^{\prime}<r$. It
follows that the number of bad sets is at most

$\Lambda^{\prime}=\sum_{t^{\prime}=0}^{t-1}\binom{t}{t^{\prime}}\sum_{r^{\prime}=1}^{r}L(t^{\prime},r^{\prime})L(t^{\prime}+r^{\prime},r-r^{\prime})+\sum_{r^{\prime}=1}^{r-1}L(t,r^{\prime})L(t+r^{\prime},r-r^{\prime}).$

Accordingly, if we define $\mathcal{R}_{1}$ to consist of all good
$R\in\mathcal{R}$, then
$|\mathcal{R}_{1}|\geq\Lambda_{1}:=L(t,r)-\Lambda^{\prime}$.

The next step is constructing $\mathcal{R}_{2}$. To that end, consider a graph
whose vertices are the sets in $\mathcal{R}_{1}$, and in which two vertices
$R_{1},R_{2}$ are connected if they are not disjoint. We will show that the
graph has bounded degree, and so a large independent set.

If $R_{1},R_{2}\in\mathcal{R}_{1}$ are not disjoint then there is some $i\in
R_{1}$ such that $i\in R_{2}$. Given $i\in R_{1}$, the induction hypothesis
shows that the number of possible $R_{2}$ is $L(t+1,r-1)$, since
$R_{2}\setminus\\{i\\}$ is a subset of $[n]$ of size $r-1$, disjoint from
$T\cup\\{i\\}$, such that $C(T\cup\\{i\\}\cup(R_{2}\setminus\\{i\\}))\neq 0$.
Since there are $r$ choices for $i$, this shows that the degree of every
vertex in the graph is at most $rL(t+1,r-1)$.

A simple greedy algorithm now constructs a subset
$\mathcal{R}_{2}\subseteq\mathcal{R}_{1}$ of size at least
$\Lambda_{2}:=\Lambda_{1}/(rL(t+1,r-1)+1)$.

In order to construct $\mathcal{R}_{3}$, we consider a hypergraph on the
vertex set $\mathcal{R}_{2}$. For each $T^{\prime}\subseteq T$ and $s\leq d$
such that $|T^{\prime}|+rs>d$, we add a hyperedge $\\{R_{1},\ldots,R_{s}\\}$
(where all $R_{i}$ are different) if there exist non-empty
$R^{\prime}_{i}\subseteq R_{i}$ such that $C(T^{\prime}\cup
R^{\prime}_{1}\cup\cdots\cup R^{\prime}_{s})\neq 0$ (we define $C(S)=0$ if
$|S|>d$). We will show that this graph contains few hyperedges, specifically
at most $K_{t,r}|\mathcal{R}_{2}|^{s-1}$ hyperedges of uniformity $s$.

Let $T^{\prime}\subseteq T$ have size $t^{\prime}$ and let $s\leq d$ be such
that $t^{\prime}+rs>d$. We want to bound the number of sets
$\\{R_{1},\ldots,R_{s}\\}$ (where all $R_{i}$ are different) such that
$C(T^{\prime}\cup R^{\prime}_{1}\cup\cdots\cup R^{\prime}_{s})\neq 0$ for some
non-empty $R^{\prime}_{i}\subseteq R_{i}$. If $R^{\prime}_{i}=R_{i}$ for all
$i$ then $|T^{\prime}\cup R^{\prime}_{1}\cup\cdots\cup
R^{\prime}_{s}|=t^{\prime}+rs>d$, and so $C(T^{\prime}\cup
R^{\prime}_{1}\cup\cdots\cup R^{\prime}_{s})=0$. Therefore $R^{\prime}_{i}\neq
R_{i}$ for some $i$. By rearranging the indices, we can assume that
$R^{\prime}_{s}\neq R_{s}$.

There are at most $|\mathcal{R}_{2}|^{s-1}$ many choices for
$R_{1},\ldots,R_{s-1}$. For each choice of distinct $R_{1},\ldots,R_{s-1}$,
there are at most $2^{sr}$ many choices of non-empty
$R^{\prime}_{1},\ldots,R^{\prime}_{s-1}$. Given
$R^{\prime}_{1},\ldots,R^{\prime}_{s-1}$ of combined size $u$ and given
$r^{\prime}\in\\{1,\ldots,r-1\\}$, the induction hypothesis shows that there
are at most $L(t^{\prime}+u,r^{\prime})$ many sets
$R^{\prime}_{s}\subseteq[n]$ of size $r^{\prime}$, disjoint from
$T^{\prime}\cup R^{\prime}_{1}\cup\cdots\cup R^{\prime}_{s-1}$, such that
$C(T^{\prime}\cup R^{\prime}_{1}\cup\cdots\cup R^{\prime}_{s})\neq 0$. For
each such $R^{\prime}_{s}$, the induction hypothesis shows that there are at
most $L(t+r^{\prime},r-r^{\prime})$ many sets
$R^{\prime\prime}_{s}\subseteq[n]$ disjoint from $T\cup R^{\prime}_{s}$ such
that $C(T\cup R^{\prime}_{s}\cup R^{\prime\prime}_{s})\neq 0$. Altogether, the
number of hyperedges of uniformity $s$ is at most

$\sum_{t^{\prime}=0}^{t}\binom{t}{t^{\prime}}|\mathcal{R}_{2}|^{s-1}2^{sr}\sum_{u=0}^{d}\sum_{r^{\prime}=1}^{r-1}L(t^{\prime}+u,r^{\prime})L(t+r^{\prime},r-r^{\prime}),$

where $L(t^{\prime},r^{\prime})=0$ if $t^{\prime}+r^{\prime}>d$. Hence we can
find a constant $K_{t,r}$ (depending on known $L(t^{\prime},r^{\prime})$) such
that the number of hyperedges of uniformity $s$ is at most
$K_{t,r}|\mathcal{R}_{2}|^{s-1}$.

Suppose now that we sample a subset of $\mathcal{R}_{2}$ by including each
$R\in\mathcal{R}_{2}$ with probability $p=|\mathcal{R}_{2}|^{-(1-1/d)}$, and
then removing all $R$ which are incident to any surviving hyperedge. The
expected number of surviving $R$ is at least

$p|\mathcal{R}_{2}|-\sum_{s=1}^{d}sp^{s}K_{t,r}|\mathcal{R}_{2}|^{s-1}=|\mathcal{R}_{2}|^{1/d}-K_{t,r}\sum_{s=1}^{d}s|\mathcal{R}_{2}|^{s/d-1}\geq|\mathcal{R}_{2}|^{1/d}-K_{t,r}d^{2}.$

In particular, we can find a subset $\mathcal{R}_{3}$ of size at least
$\Lambda_{3}:=\Lambda_{2}^{1/d}-K_{t,r}d^{2}$ which spans no hyperedges. That
is, if $R_{1},\ldots,R_{s}\in\mathcal{R}_{3}$ and $C(S)\neq 0$ for some
$S\subseteq T\cup R_{1}\cup\cdots\cup R_{s}$ intersecting all of
$R_{1},\ldots,R_{s}$, then $|S\cap T|+rs>d$.

We construct $\mathcal{R}_{4}$ by applying Ramsey’s theorem. For every $s$
such that $rs\leq d$, we color every subset
$\\{R_{1},\ldots,R_{s}\\}\subseteq\mathcal{R}_{3}$ of size $s$ by the function

$T^{\prime}\mapsto\sum_{\begin{subarray}{c}R^{\prime}_{1}\subseteq
R_{1},\ldots,R^{\prime}_{s}\subseteq R_{s}\\\
R^{\prime}_{1},\ldots,R^{\prime}_{s}\neq\emptyset\end{subarray}}C(T^{\prime}\cup
R^{\prime}_{1}\cup\cdots\cup R^{\prime}_{s}).$

where $T^{\prime}$ ranges over all subsets of $T$ (recall that we defined
$C(S)=0$ when $|S|>d$). According to Lemma 3.3, all summands belong to a
finite set $\mathcal{D}$, and so the sum attains one of at most
$|\mathcal{D}|^{2^{rs}}$ possible values. Consequently, the number of colors
is at most $(2^{t})^{|\mathcal{D}|^{2^{rs}}}$. If $\mathcal{R}_{3}$ is large
enough then we can apply Ramsey’s theorem to obtain a subset
$\mathcal{R}_{4}\subseteq\mathcal{R}_{3}$ of size $k$, and values
$\Gamma(T^{\prime},s)$ for all $T^{\prime}\subseteq T$ and $s\leq\lfloor
d/r\rfloor$, such that all distinct $R_{1},\ldots,R_{s}\in\mathcal{R}_{4}$
satisfy

$\sum_{\begin{subarray}{c}R^{\prime}_{1}\subseteq
R_{1},\ldots,R^{\prime}_{s}\subseteq R_{s}\\\
R^{\prime}_{1},\ldots,R^{\prime}_{s}\neq\emptyset\end{subarray}}C(T^{\prime}\cup
R^{\prime}_{1}\cup\cdots\cup R^{\prime}_{s})=\Gamma(T^{\prime},s).$

We can extend the definition of $\Gamma$ to larger $s$. The construction of
$\mathcal{R}_{3}$ guarantees that $\Gamma(T^{\prime},s)=0$ if
$|T^{\prime}|+rs>d$. Moreover, since all $R\in\mathcal{R}_{4}$ are good, we
know that $\Gamma(T^{\prime},1)=0$ if $T^{\prime}\neq T$ and $\Gamma(T,1)\neq
0$.

At this point, we can explain how to choose $L(t,r)$. We choose $L(t,r)$ so
that the condition $|\mathcal{R}_{3}|\geq\Lambda_{3}$ is strong enough in
order for the application of Ramsey’s theorem detailed above to go through.

Let $V$ consist of the union of all sets in $\mathcal{R}_{4}$. The next step
is to choose a set $P=\\{p_{1},\ldots,p_{k}\\}\subseteq[n]$ of size $k$ such
that $C(S)=0$ for any subset $S\subseteq T\cup V\cup P$ intersecting $P$. This
will be possible assuming that $n$ is large enough.

We choose $P$ in $k$ steps. In the $i$’th step, given the choice of
$p_{1},\ldots,p_{i-1}$, we choose $p_{i}$. For any $e<d$ and any subset
$S^{\prime}\subseteq T\cup V\cup\\{p_{1},\ldots,p_{i-1}\\}$ of size $e$, there
are at most $L(e,1)$ many $p\notin S^{\prime}$ such that
$C(S^{\prime}\cup\\{p\\})\neq 0$. Therefore we can find a suitable $p_{i}$ as
long as

$n>N_{i}(t,r):=t+kr+i-1+\sum_{e=0}^{d-1}\binom{t+kr+i-1}{e}L(e,1).$

Accordingly, we choose $N(t,r)=\max(k+d,N_{k-1}(t,r)+1)$. This ensures that we
can choose the set $P$.

Let $T^{\prime}$ be an inclusion-minimal subset of $T$ such that
$\Gamma(T^{\prime},s)\neq 0$ for some $s>0$, and let
$t^{\prime}=|T^{\prime}|$. This means that $\Gamma(T^{\prime\prime},s)=0$ for
all $T^{\prime\prime}\subsetneq T^{\prime}$ and $s>0$. Such a choice is
possible since $\Gamma(T,1)\neq 0$. Also, let $s^{\prime}>0$ be the minimal
value such that $\Gamma(T^{\prime},s^{\prime})\neq 0$.

Let $w$ be such that $t^{\prime}+rw\leq k$. The value of $f$ on an input
consisting of $T^{\prime}$ together with the union of $w$ sets from
$\mathcal{R}_{4}$ and $k-t^{\prime}-rw$ elements from $P$ is

$\sum_{T^{\prime\prime}\subseteq
T^{\prime}}\sum_{s=0}^{d}\binom{w}{s}\Gamma(T^{\prime\prime},s)=\sum_{T^{\prime\prime}\subseteq
T^{\prime}}\Gamma(T^{\prime\prime},0)+\sum_{s=s^{\prime}}^{\lfloor\frac{d-t^{\prime}}{r}\rfloor}\binom{w}{s}\Gamma(T^{\prime},s).$

This is a polynomial $Q(w)$ of degree at most
$\lfloor\frac{d-t^{\prime}}{r}\rfloor$ such that
$Q(0),\ldots,Q(\lfloor\frac{k-t^{\prime}}{r}\rfloor)\in A$, and so since
$k\geq\kappa(A,d)$, $Q$ is constant. However, by construction,
$Q(s^{\prime})-Q(s^{\prime}-1)=\Gamma(T^{\prime},s^{\prime})\neq 0$. We have
reached the required contradiction, completing the proof. ∎

###  3.5 The parameter $k(A,d)$

In this subsection we show that $k(A,d)=\kappa(A,d)$, and prove that
$k(A,d)=|A|d$ when $A$ is an arithmetic progression, thus proving Lemma 3.2.
We start by giving an alternative formula for $\kappa(A,d)$ in terms of the
parameter $W(A,d)$ introduced in Section 1, which is the minimal value $W$
such that every degree $d$ polynomial $P$ satisfying $P(0),\ldots,P(W)\in A$
is constant.

Before giving the formula for $\kappa(A,d)$ in terms of $W(A,d)$, let us show
that $W(A,d)$ is indeed well-defined.

######  Lemma 3.7.

If $A\subseteq\mathbb{R}$ is a set containing at least two elements and $d\geq
1$ then $d<W(A,d)\leq|A|d$.

###### Proof.

Suppose that $P$ is a degree $d$ polynomial. We will show that if
$P(0),\ldots,P(W)\in A$ for $W=|A|d$ then $P$ is constant, and so
$W(A,d)\leq|A|d$. According to the pigeonhole principle, there is $a\in A$
such that $P(i)=a$ for at least $d+1$ many $i\in\\{0,\ldots,W\\}$. Since every
non-constant degree $d$ polynomial has at most $d$ roots, we conclude that $P$
is constant.

In order to show that $W(A,d)>d$, we will exhibit a non-constant degree $d$
polynomial $P$ satisfying $P(0),\ldots,P(d)\in A$. Let $a,b\in A$ be two
distinct elements of $A$. We define

$P(x)=a+(b-a)\prod_{i=0}^{d-1}\frac{x-i}{d-i}.$

By construction, $P(0)=\cdots=P(d-1)=a$ and $P(d)=b$. ∎

Here is the formula for $\kappa(A,d)$ in terms of $W(A,d)$. It is the minimal
$\kappa$ which satisfies the following conditions:

  1. 1.

$\kappa\geq d+1$.

  2. 2.

$\kappa-e\geq W(A,d-e)$ for all $e\in\\{0,\ldots,d-1\\}$.

  3. 3.

$\lfloor\frac{\kappa-t}{r}\rfloor\geq W(A,s)$ whenever $r,s\geq 1$ and
$t+rs\leq d$.

This results in the following formula, whose proof is immediate.

######  Lemma 3.8.

If $A\subseteq\mathbb{R}$ is a finite set containing at least two elements and
$d\geq 1$ then

$\kappa(A,d)=\max\left(d+1,\max_{0\leq e\leq
d-1}e+W(A,d-e),\max_{\begin{subarray}{c}1\leq s\leq d\\\ 1\leq r\leq\lfloor
d/s\rfloor\end{subarray}}d-rs+rW(A,s)\right).$

Using this formula, we can prove Lemma 3.2.

###### Proof of Lemma 3.2.

Lemma 3.7 shows that $W(A,d)\geq d+1$. Consequently, $0+W(A,d-0)\geq d+1$, and
so we can drop the first term in the formula in Lemma 3.8. Taking $s=d-e$ and
$r=1$, the third term recovers the second term. Therefore

$\kappa(A,d)=\max_{\begin{subarray}{c}1\leq s\leq d\\\ 1\leq r\leq\lfloor
d/s\rfloor\end{subarray}}d+r(W(A,s)-s)=\max_{1\leq s\leq
d}d+\left\lfloor\frac{d}{s}\right\rfloor(W(A,s)-s),$

since $W(A,s)\geq s+1$ according to Lemma 3.7. The expression on the right-
hand side coincides with the formula for $k(A,d)$ in the statement of Theorem
1.2.

Suppose now that $A$ is an arithmetic progression, say
$A=\\{a,a+b,\ldots,a+(m-1)b\\}$, where $m=|A|$. The polynomial $P(x)=a+bx$
shows that $W(A,1)>|A|-1$, and so $W(A,1)=|A|$ according to Lemma 3.7. Taking
$s=1$ in the formula for $k(A,d)$, this shows that $k(A,d)\geq
d+d(|A|-1)=|A|d$. On the other hand, for every $s\in\\{1,\ldots,d\\}$ we have

$d+\left\lfloor\frac{d}{s}\right\rfloor(W(A,s)-s)\leq
d+\frac{d}{s}(s|A|-s)=|A|d,$

using Lemma 3.7. Therefore $k(A,d)=|A|d$. ∎

When $A$ is not an arithmetic progression, it is not necessarily the case that
$k(A,d)=|A|d$. For example, $k(A,1)=W(A,1)$ is the length of the longest
arithmetic progression contained in $A$.

Here are the values of $W(A,d),k(A,d)$ for several choices of $A$:

$\begin{array}[]{c|*{5}{c}|*{10}{c}}\hbox{\multirowsetup A}&\lx@intercol\hfil
W(A,d)\hfil\lx@intercol\vrule\lx@intercol&\lx@intercol\hfil
k(A,d)\hfil\lx@intercol\\\ \cline{2-16}\cr&1&2&3&4&5&\lx@intercol\hfil
1\hfil\lx@intercol&\lx@intercol\hfil 2\hfil\lx@intercol&\lx@intercol\hfil
3\hfil\lx@intercol&\lx@intercol\hfil 4\hfil\lx@intercol&\lx@intercol\hfil
5\hfil\lx@intercol\\\
\hline\cr\\{0,1\\}&2&4&4&6&6&2&[1]&4&[1,2]&6&[1]&8&[1,2]&10&[1]\\\
\\{0,1,3\\}&2&6&6&7&8&2&[1]&6&[2]&7&[2]&12&[2]&13&[2]\\\
\\{0,1,4,5,20\\}&2&5&7&8&8&2&[1]&5&[2]&7&[3]&10&[2]&11&[2]\\\
\\{0,1,27,126,370\\}&2&4&4&10&10&2&[1]&4&[1,2]&6&[1]&10&[4]&11&[4]\end{array}$

The numbers in squares indicate that values of $s$ for which $k(A,d)$ is
attained.

##  4 Final remarks

#### Another threshold

Theorem 2.3, proved in [FI19a], states that if $C^{d}\leq k\leq n-C^{d}$ and
$f$ is a Boolean degree $d$ function on $\binom{[n]}{k}$, then $f$ is a
$KC^{d}$-junta. The result proved in [FI19a] is in fact stronger: under the
same assumptions, there is a Boolean degree $d$ function $g$ _on the Boolean
cube_ $\\{0,1\\}^{n}$ such that $f$ is the restriction of $g$ to the slice.
This implies the junta conclusion since every Boolean degree $d$ function on
the Boolean cube is an $O(2^{d})$-junta [NS94, CHS20, Wel20].

In this paper, we answer one open question raised in [FI19a]: we find the
minimal $k=k(d)$ such that every Boolean degree $d$ function on
$\binom{[n]}{k}$, where $n\geq 2k$, is a junta. Another open question in
[FI19a] asks for the minimal $\ell=\ell(d)$ such that every Boolean degree $d$
function on $\binom{[n]}{\ell}$, where $n\geq 2\ell$, is the restriction of a
Boolean degree $d$ function on $\\{0,1\\}^{n}$. Clearly, $\ell(d)\geq k(d)$.
Is it the case that $\ell(d)=k(d)$? When $d=1$, this follows from [FI19b].

More generally, we can define $\ell(A,d)$ for any finite $A$. It is not always
the case that $\ell(A,d)=k(A,d)$. For example, if $A=\\{0,5,7,8,12,13,15\\}$
then $k(A,1)=2$ whereas $\ell(A,1)=3$. Indeed, the function
$5x_{1}+7x_{2}+8x_{3}$ is $A$-valued on $\binom{[n]}{2}$ for any $n\geq 4$,
but is not the restriction of any $A$-valued degree $1$ function on
$\\{0,1\\}^{n}$.

#### Multislice

The _multislice_ is the generalization of the slice to functions on
$\\{0,\ldots,m-1\\}$ for arbitrary $m$. Given a partition
$n=\lambda_{0}+\cdots+\lambda_{m-1}$, the corresponding multislice consists of
all vectors in $\\{0,\ldots,m-1\\}^{n}$ containing exactly $\lambda_{i}$
coordinates whose value is $i$. Given another partition
$k=k_{1}+\cdots+k_{m-1}$, we can consider the family of multislices with
$\lambda_{0}\geq k$ and $\lambda_{1}=k_{1},\ldots,\lambda_{m-1}=k_{m-1}$. We
conjecture that all of our results extend to this setting.

## References

  * [CHS20] John Chiarelli, Pooya Hatami, and Michael Saks.  An asymptotically tight bound on the number of relevant variables in a bounded degree Boolean function.  Combinatorica, 40(2):237–244, 2020.
  * [FI19a] Yuval Filmus and Ferdinand Ihringer.  Boolean constant degree functions on the slice are juntas.  Discrete Mathematics, 342(12):111614, 2019.
  * [FI19b] Yuval Filmus and Ferdinand Ihringer.  Boolean degree 1 functions on some classical association schemes.  Journal of Combinatorial Theory, Series A, 162:241–270, 2019.
  * [Fil16] Yuval Filmus.  Orthogonal basis for functions over a slice of the Boolean hypercube.  Electronic Journal of Combinatorics, 23(1):P1.23, 2016.
  * [FM19] Yuval Filmus and Elchanan Mossel.  Harmonicity and invariance on slices of the Boolean cube.  Probability Theory and Related Fields, 175(3–4):721–782, 2019\.
  * [NS94] Noam Nisan and Márió Szegedy.  On the degree of Boolean functions as real polynomials.  Comput. Complexity, 4(4):301–313, 1994.  Special issue on circuit complexity (Barbados, 1992).
  * [vzGR97] Joachim von zur Gathen and James R. Roche.  Polynomials with two values.  Combinatorica, 17(3):345–362, 1997.
  * [Wel20] Jake Wellens.  Relationships between the number of inputs and other complexity measures of Boolean functions.  arXiv, abs/2005.00566, 2020.