# Broadband chip-based source of a quantum noise with electrically-
controllable beam splitter

E. A. Vashukevich1, V. V. Lebedev2,3, I. V. Ilichev2,3, P. M. Agruzov2,3, A.
V. Shamrai2,3, V. M. Petrov3, T. Yu. Golubeva1 1 Saint Petersburg State
University, Universitetskaya nab. 7/9, St. Petersburg, 199034 Russian
Federation,
2 Ioffe Institute, Politekhnicheskaya str. 29, St. Petersburg, 194021 Russian
Federation
3 ITMO University, Kronverksky pr. 49, St. Petersburg, 197101 Russian
Federation

###### Abstract

For the first time, the theory and practical realization of a broadband
quantum noise generator based on original integrated optical beam splitter in
the form of a Mach-Zehnder interferometer is demonstrated. The beam splitter
with a double output, made on a lithium niobate substrate, provided accurate
electro-optical balancing of the homodyne quantum noise detection circuit.
According to our knowledge, the experimentally obtained excess of quantum
noise over classical noise by 12 dB in the frequency band over 4 GHz, which is
the best parameters of quantum noise generators known from the literature.

##  I Introduction

Quantum noise generators and random number generators based on them are on
demand for many applications [1, 2, 3]. The homodyne detection of vacuum
fluctuations is one of the most efficient techniques to build a quantum noise
generator. As a rule, quantum noise generators are used for the subsequent
development of quantum random number generators. To do this, the analog signal
must be converted into a digital code [4, 5, 6, 7, 8, 9, 10].

Quantum vacuum fluctuations are used as a physical source of entropy of the
noise generator. Its technical implementation is based on a local oscillator,
beam splitter, and balanced detection scheme, that provides suppression of
classical noise and registration of quantum shot noise. From the point of view
of the informational throughput of the random number generator, one of the
most important parameter here is the frequency band of the quantum noise at
the output of the balanced detector [6]. The currently experimentally achieved
maximum band of homodyne detection of vacuum fluctuations is about 1 GHz [8,
9], which is due to the use of schemes on the so-called ”volumetric” optics.

Integrated optical beam splitters based on silicon optical waveguides [10] can
only partially solve the problems of volumetric optics. Sufficiently high
absorption and photosensitivity at telecommunications wavelengths (1500 - 1600
nm) produce sources of additional classical noise and limit the maximum
optical power, and the thermoelectric control used in [10] for active tuning
has a high inertia and is not suitable for broadband devices. This did not
allow the generation of quantum noise in the band of more than 150 MHz.

To construct a quantum noise generator, a scheme based on balanced homodyne
detection of a vacuum field is widely used. However, such an implementation of
the generator has a significant limitation: the lack of the ability to control
interference when mixing fields on the beam splitter. Violation of the ideal
symmetry of the beam splitter coefficients leads to a violation of the balance
on the detectors, which negatively affects the visibility of the signal, and,
as a result, the speed of random number generation. To solve this problem and
implement the control of balanced detector, we used an integrated optical
Mach-Zehnder interferometer formed by input Y-branch, output X-coupler, and
with the electro-optical control of phase difference between arms of the
interferometer.

Note that the Y-branch despite the presence of only one input port (Fig. 1)
serves as a mixer of fields of a local oscillator and vacuum fluctuations.
Vacuum fluctuations penetrate in the Y-branch from substrate as leakage modes.
It is not difficult to prove that there is a second port, given the unitarity
of conversion of the input radiation to the output produced by the beam
splitter. By organizing the illumination of the circuit from the output side
and varying the phase difference of the fields, it is possible to see the
points of the output radiation through the substrate in a situation where the
central the mode is suppressed by destructive interference. It is these output
points that will correspond to the second, unlit (vacuum) input of the beam
splitter when the circuit is normally illuminated from left to right. Thus, we
will describe the input Y-branch of the scheme under consideration as a four-
port device [11] like a X-coupler or volume beam splitter, on one of the ports
of which there is a field in the vacuum state. Then the whole system under
consideration is similar to the usual Mach-Zehnder interferometer with two
inputs and two outputs.

##  II Theory

Let us consider the case when the strong classic field from the local
oscillator $E_{LO}(z,t)$ enters the beam splitter at the input 1, and only the
vacuum field $\hat{E}_{vac}(z,t)$ enters at the input 2 (Fig. 1). After mixing
on the first beam splitter, the fields are given a relative phase delay
$\phi$, after which the fields are mixed again on the second beam splitter and
detected. It is the phase difference $\phi$ that acts as a parameter that
additionally controls the interference conditions on the second beam splitter.
The transformation of the fields on the first and second beam splitters can be
set by matrices $M_{BS,1},M_{BS,2}$:

$\displaystyle
M_{BS,i}=\begin{pmatrix}\cos{\left(\alpha_{i}\right)}&\sin{\left(\alpha_{i}\right)}\\\
\sin{\left(\alpha_{i}\right)}&-\cos{\left(\alpha_{i}\right)}\end{pmatrix},\;\;i=1,2.$
(1)

Here the parameters $\alpha_{1},\alpha_{2}$ are set so the
$\cos{\left(\alpha_{i}\right)}$ is equal to the amplitude transmission
coefficient of the beam splitter $t_{i}$, and the
$\sin{\left(\alpha_{i}\right)}$ is correspondingly equal to the reflection
coefficient $r_{i}$.

Figure 1:  a) Definition of the coefficients $r_{i}$ and $t_{i}$ for the
volumetric beam splitter cube. b), c) the possible types of tunable integrated
optical beam splitters. b) beam splitter, based on two X-couplers, that form
the Mach-Zehnder interferometer with 2 inputs and 2 outputs; the input 1 is
directly connected by optical fiber to the source of $E_{LO}$, only the mode
of the local oscillator gets to this input; the input 2 is open, only the
modes of vacuum fluctuations corresponding to the modes of the optical
waveguide enters this input; c) based on one Y-branch and one X-coupler, that
form the Mach-Zehnder interferometer with 1 input and two outputs. The
additional, second input in2 for vacuum fluctuations occurs due to the leakage
modes (dashed arrows).

It can be noted that with the chosen parametrization, the conservation law
$r_{i}^{2}+t_{i}^{2}=1$ is fulfilled automatically.

The phase delay in one of the arms of the interferometer is given by the
matrix:

$\displaystyle M_{Ph}=\begin{pmatrix}\exp{\\{i\phi/2\\}}&0\\\
0&\exp{\\{-i\phi/2\\}}\end{pmatrix}$ (2)

Next, one can write down the expression for the fields at the output of the
scheme $\hat{E}_{out,1},\hat{E}_{out,2}$ in terms of the initial fields:

$\displaystyle\binom{\hat{E}_{out,1}}{\hat{E}_{out,2}}=U\binom{E_{LO}}{\hat{E}_{vac}}$
(3) $\displaystyle U=M_{BS,2}\cdot M_{Ph}\cdot M_{BS,1}$ (4)

Here the elements of the of the transformation matrix are:

$\displaystyle
U_{11}=e^{i\phi/2}\left(\cos{\left(\alpha_{1}\right)}\cos{\left(\alpha_{2}\right)}+e^{-i\phi}\sin{\left(\alpha_{1}\right)}\sin{\left(\alpha_{2}\right)}\right)$
(5) $\displaystyle
U_{12}=e^{i\phi/2}\left(\sin{\left(\alpha_{1}\right)}\cos{\left(\alpha_{2}\right)}-e^{-i\phi}\cos{\left(\alpha_{1}\right)}\sin{\left(\alpha_{2}\right)}\right)\;\;\;\;\;\;$
(6) $\displaystyle
U_{21}=e^{i\phi/2}\left(\cos{\left(\alpha_{1}\right)}\sin{\left(\alpha_{2}\right)}-e^{-i\phi}\sin{\left(\alpha_{1}\right)}\cos{\left(\alpha_{2}\right)}\right)\;\;\;\;\;\;$
(7) $\displaystyle
U_{22}=e^{-i\phi/2}\left(\cos{\left(\alpha_{1}\right)}\cos{\left(\alpha_{2}\right)}+e^{i\phi}\sin{\left(\alpha_{1}\right)}\sin{\left(\alpha_{2}\right)}\right)\;\;\;\;\;\;$
(8)

The photocurrent operators on both detectors can be written as follows:

$\displaystyle\hat{j}_{1}=\hat{E}^{\dagger}_{out,1}\hat{E}_{out,1}=(U^{*}_{11}E^{*}_{LO}+U^{*}_{12}\hat{E}^{\dagger}_{vac})$
$\displaystyle\times(U_{11}E_{LO}+U_{12}\hat{E}_{vac})$ (9)
$\displaystyle\hat{j}_{2}=\hat{E}^{\dagger}_{out,2}\hat{E}_{out,2}=(U^{*}_{21}E^{*}_{LO}+U^{*}_{22}\hat{E}^{\dagger}_{vac})$
$\displaystyle\times(U_{21}E_{LO}+U_{22}\hat{E}_{vac})$ (10)

Now, for convenience, lets move on to the quadrature components (with numeric
representation for the classical field and operator for the quantum one):
$E_{LO}=\varepsilon^{\prime}+i\varepsilon^{\prime\prime}$,
$\hat{E}_{vac}=\hat{x}+i\hat{y}$; in addition, let us denote
$|E_{LO}|^{2}=I_{LO}$. The differential signal $\hat{j}_{-}(\phi)$ can be
written as follows (we denote $\alpha_{\pm}=2(\alpha_{1}\pm\alpha_{2})$):

$\displaystyle\hat{j}_{-}(\phi)=\hat{i}_{1}-\hat{i}_{2}=\left[I_{LO}-\hat{x}^{2}-\hat{y}^{2}\right]$
$\displaystyle\times\left[\cos^{2}(\phi/2)\cos(\alpha_{-})+\sin^{2}(\phi/2)\cos(\alpha_{+})\right]$
$\displaystyle+2\left[\varepsilon^{\prime}\hat{x}+\varepsilon^{\prime\prime}\hat{y}\right]$
$\displaystyle\times\left[\cos^{2}(\phi/2)\sin(\alpha_{-})+\sin^{2}(\phi/2)\sin(\alpha_{+})\right]$
$\displaystyle-2\left[\varepsilon^{\prime}\hat{y}-\varepsilon^{\prime\prime}\hat{x}\right]\sin(\phi)\sin(2\alpha_{2})$
(11)

In the case when the beam splitters are symmetric $r_{i}=1/\sqrt{2}=t_{i}$,
the transformation matrix has a simple form:

$\displaystyle U=\begin{pmatrix}\cos{\phi/2}&i\sin{\phi/2}\\\
i\sin{\phi/2}&\cos{\phi/2}\end{pmatrix}$ (12)

The difference photocurrent with symmetric beam splitters $j^{s}_{-}(\phi)$
will be modulated by the phase difference $\phi$:

$\displaystyle\hat{j}^{s}_{-}(\phi)=(I_{LO}-\hat{x}^{2}-\hat{y}^{2})\cos{\phi}-2(\varepsilon^{\prime}\hat{y}-\varepsilon^{\prime\prime}\hat{x})\sin{\phi}\;\;\;\;$
(13)

As you can see, with the phase difference $\phi=\pi/2$ the first term
proportional to the intensity of the fields will be completely suppressed, and
homodyne detection of the quadrature components of the quantum field is
carried out in the Mach-Zehnder interferometer scheme. For simplicity, here
and further, we will select the phase of the local oscillator so that
$\varepsilon^{\prime\prime}=0$, then the difference signal can be written as
follows:

$\displaystyle\hat{j}^{s}_{-}(\pi/2)=-2\varepsilon^{\prime}\hat{y}$ (14)

Since the value of the quadrature component measured in the experiment is a
random variable, we have the opportunity to generate a sequence of truly
random numbers in the proposed scheme. As can be seen from (14), the
dispersion of the noise field y increases in proportion to the magnitude of
the field of the local oscillator.

Now we will take into account the differences between the real experimental
situation and the ideal one described above. First of all, we take into
account the possible asymmetry of the beam splitter. Lets assume that one of
the beam splitters (for example, the output one) is asymmetric, choosing
$r_{2}=\sqrt{0.49},t_{2}=\sqrt{0.51}$. Now we write down the dependence of the
difference current in the case of an asymmetric beam splitter
$\hat{j}^{a}_{-}(\phi)$ on the phase, leaving the field of the local
oscillator purely real:

$\displaystyle\hat{j}^{a}_{-}(\phi)=$ $\displaystyle
0.9998\cos(\phi)\left(I_{LO}^{2}-\hat{x}^{2}-\hat{y}^{2}\right)$ (15)
$\displaystyle-2\cdot 0.9998\sin(\phi)\varepsilon^{\prime}\hat{y}-2\cdot
0.02\varepsilon^{\prime}\hat{x}$

As one can see, the second quadrature component begins to appear in the
signal. Moreover, the last term in (15) is phase-independent. However, the
contribution from the first term, proportional to the intensity of the fields,
which is most harmful for noise generation, can be completely compensated by
choosing a suitable phase of the modulator. When the phase difference is
$\phi=\frac{\pi}{2}$ we will get:

$\displaystyle\hat{j}^{a}_{-}(\frac{\pi}{2})=-2\cdot
0.9998\varepsilon^{\prime}\hat{y}-2\cdot 0.02\varepsilon^{\prime}\hat{x}$ (16)

Note that the obtained form of recording the signal allows us to talk about
the measurement of the generalized quadrature of the noise field, that is, the
measurement in the basis expanded by some angle. Since the distribution of the
vacuum field on the phase plane is absolutely symmetric, the reversal of the
basis does not introduce any changes in the operation of the noise generator.
Thus, in the absence of other factors of the imperfection of the scheme, the
asymmetry of the beam splitter would be insignificant for the generation of
random numbers.

The key factor here, however, is the fact that if the beam splitter is not
symmetric, an additional classical noise component will be present in the
difference current, which is completely subtracted when considering a
symmetric circuit. We show this explicitly by introducing losses
$\eta_{1},\eta_{2}$, in both arms of the interferometer associated with the
presence of classical noise. Then, instead of the Eq. (4) used above, the
field at the output of the interferometer will be set by the expression:

$\displaystyle\binom{\hat{E}_{out,1}}{\hat{E}_{out,2}}=\tilde{U}\binom{E_{LO}}{\hat{E}_{vac}}$
(17) $\displaystyle\tilde{U}=M_{BS,2}\cdot\begin{pmatrix}\eta_{1}&0\\\
0&\eta_{2}\end{pmatrix}M_{Ph}\cdot M_{BS,1}$ (18)

We repeat all the calculations made without taking into account losses,
preserving the assumptions made earlier about the symmetry of the first beam
splitter and the realness of the field of the local oscillator. The difference
current $\hat{j}_{-}(\phi)$ will then have the form:

$\displaystyle\hat{j}_{-}(\phi)=\frac{1}{2}\cos(2\alpha_{2})\left(\eta_{1}^{2}-\eta_{2}^{2}\right)\left(I_{LO}+\hat{x}^{2}+\hat{y}^{2}\right)$
$\displaystyle+\eta_{1}\eta_{2}\sin(2\alpha_{2})\cos(\phi)\left(I_{LO}-\hat{x}^{2}-\hat{y}^{2}\right)$
$\displaystyle+\varepsilon^{\prime}\hat{x}\cos(2\alpha_{2})\left(\eta_{1}^{2}+\eta_{2}^{2}\right)-2\eta_{1}\eta_{2}\varepsilon^{\prime}\hat{y}\sin(2\alpha_{2})\sin(\phi)\;\;\;\;$
(19)

In the case of symmetrical output beam splitter $\alpha_{2}=\pi/4$, the
expression (19) is reduced by the choice of phase $\phi=\pi/2$ to (14) with
extra multiplication by factor $\eta_{1}\eta_{2}$. However, as one can see,
for any asymmetric beam splitter in (19), there remains a phase-independent
first term containing the intensity of the field of the local oscillator,
which will dominate the signal of interest. This term can be removed by
analyzing the phase $\phi$ and selecting it so that the following equation is
performed:

$\displaystyle\cos(\phi)\approx\frac{\left(\eta_{1}^{2}-\eta_{2}^{2}\right)}{2\eta_{1}\eta_{2}}\cot(2\alpha_{2})$
(20)

Such a choice of the modulator phase leads to complete mutual compensation of
the first two terms in expression (19). As a result, the expression for the
difference photocurrent can again be represented as the amplification of the
generalized noise quadrature (similar to Eq. (15)), where the gain is lesser
than the original one by a factor of $\eta_{1}\eta_{2}$. It is interesting to
estimate the amount of phase adjustment required for balancing the circuit.
For example, for $\cos(2\alpha_{2})=-0.02,\eta_{1}=0.9,\eta_{2}=0.85$ to
compensate for the term containing $I_{LO}$, we need to add to the phase
$\phi=\pi/2$ only the $3\times 10^{-4}\pi$. Thus, the use of a phase modulator
makes it possible to balance the circuit in the presence of not only
asymmetric detector operation, but also various classical noises in the
interferometer channels.

##  III Experiment

We have proposed and experimentally implemented a broadband quantum noise
generator using an integrated optical Mach-Zehnder interferometer with a
single input and a double output as an electrically-controlled beam splitter
(BS), made on the basis of optical waveguides in a lithium niobate crystal
substrate (Fig. 2). The $\hbox{LiNbO}_{3}$ congruent single crystal plate of
the X-cut had the size $5\times 50\times 1$mm3. The single-mode channel
optical waveguides were manufactured using the technology of thermal diffusion
of Ti-ions [12]. Light propagated along Y crystallographic axes. A push-pull
electrodes was deposited along one of the arms of the interferometer, which
made it possible to adjust the amplitude transmission coefficient of the beam
splitter $t_{i}$ using the electro-optical effect.

Figure 2:  The experimental realization: quantum noise generator based on
integrated-optic Mach-Zehnder beam splitter with the electrical control. LO is
the local oscillator, BS is the beam splitter, FA is the fiber-optic assembly,
BD is the balanced detector, OPS is the operating point control system.

A single frequency laser with distributed feedback with a wavelength of 1552
nm, a radiation line width of 170 kHz, and a power of 100 mW was used as a
local oscillator (LO).

A special attention was paid to the design of the balanced detector (BD). The
radiation from the beam splitter outputs was transmitted through the fiber
assembly (FA) to the InGaAs-pin photodiodes (A,B) that form the balanced
detector. The difference of the optical paths of the fiber-optic assembly did
not exceed 0.1 of the operating wavelength.

The band of each photodiode was 10 GHz, which provided the band of the
balanced detector above 4 GHz. For this purpose, photodiodes with the closest
possible frequency response and the same sensitivity of $\approx$0.78A/W were
selected. A high saturation current ($\sim$ 30 mA) and a dark current of less
than 1 $\mu$A provided a high dynamic range. The operating point control
system (OPC) provided accurate balancing of output currents ($<$0.1$\%$) [13].
To suppress classical noise, anti-phase subtraction of synchronous signals was
provided by equalizing the optical and electrical paths in the balanced
circuit.

The efficiency of the balanced photodetector was evaluated by suppressing
common-mode interference. To emulate common-mode signal the laser radiation
was modulated in amplitude and differencial signal was applied to the tunable
integrated optical BS. The suppression was defined as the ratio of the
frequency response to a differential signal to the frequency response to a
common-mode signal. The common-mode interference suppression by more than 15
dB is observed in the band over 3 GHz. The decrease in the suppression
efficiency with increasing frequency was due to increased requirements for the
accuracy of performing phase matching and the difference in the frequency
response of photodiodes.

Figure 3:  Experimental results. a): the spectral power density $N(f)$ at the
output of balanced detector. 1: local oscillator OFF, 2: local oscillator ON;
b): the electrical power $P_{el}$ at the output of the balanced detector as a
function of optical power $P_{opt}$ of the local oscillator (LO).

A part of the electrical signal from the output of the balanced detector was
sent to OPC unit, which generated a feedback signal a control voltage $\pm
U_{C}$. This voltage was applied to electrodes, which made it possible to
change the phase delay between the arms, and, consequently, to control the
splitting coefficient of the beam splitter. The accuracy of the splitting
control was not worse as 0.1$\%$ in power.

Measurements of the noise signal at the output showed an excess of the
spectral power density of the detected quantum noise by an amount of more than
12 dB above the level of technical noise of the measuring system with a preamp
in the band of more than 4 GHz (Fig. 3, a). The level of classical noise
caused by random intensity noise (RIN) of the laser has a value much smaller
than the quantum ones, which is confirmed by the proximity to the linear
dependence characteristic of quantum shot noise (Fig. 3, b). The power level
of the recorded quantum noise is in good agreement with the theoretical
estimation, which predicts a linear growth:

$\displaystyle N(f)=2qP_{opt}AR_{0}|H^{2}_{pd}(f)|,$ (21)

where $N(f)$ is the spectral power density, $q$ is the electron charge,
$P_{opt}$ is the power on the input of the photodiodes, $A$ is the direct
current sensitivity of the photodiodes, $H_{pd}(f)$ is the transfer function
of the balanced photodetector, $R_{0}$ is the output loading resistor of the
balanced detector.

According to the estimates obtained from the literature, we have developed a
broadband quantum noise generator, probably with the highest parameters for
the present time. Experimentally, an excess of quantum noise over classical
noise was obtained by more than 12 dB in the band of more than 3 GHz, which is
the best characteristics for this type of generators known from the
literature. This generator is based on homodyne detection of quantum
fluctuations, using a controlled beam splitter based on a Mach-Zehnder
waveguide interferometer on a lithium niobate substrate and a high-frequency
balanced detector.

##  IV Conclusion

We have designed and experimentally implemented a quantum noise source with
remarkable characteristics. Three factors mainly determine the broadband
source with a spectral bandwidth of more than 3 GHz.

First of all, such a broad generation band turns out to be possible due to the
integrated-optical chip-based implementation of homodyne detection with the
field mixer in the form of Y-branch. It should be noted that, in contrast to
traditional volumetric beam splitters or waveguide X-couplers, the reflection
and transmission coefficients of which depend quite critically on the the
light wavelengtht [14], integrated optical Y-branches are much more broadband
elements. Thus, the spectral width of our generator is determined by the
spectral characteristics of the detectors, not the beam splitters. This factor
allowed us to build a theory without considering the spectral dependence of
the beam splitter coefficients.

The second important factor that makes it possible to achieve record results
is developing a feedback loop that allows us to quickly and accurately control
the delay in the arm of the Mach-Zehnder interferometer. As shown in the
theoretical part of the paper, fine tuning of the balance allows getting rid
of the influence of classical noises in the system. The presence of asymmetric
losses in the interferometer channels leads to degeneration of interference
and the uncompensated currents proportional to the homodyne intensity mixing
into the signal. Even a weak asymmetry can significantly impair the signal
visibility due to large values of the homodyne amplitude. Controlling the
interference phase using a feedback loop enabled the achievement of the
visibility of the quantum noise signal above the classical noise by more than
12 dB.

It should be noted that if we imagine an ideal situation in which there are no
classical noises in the system, then the asymmetry of the beam splitter does
not worsen the observation parameters of quantum noise but only rotates the
observation basis, which is not significant for symmetric noise distribution.
Correctness of the quantum-mechanical description of the measurement in the
presence of a feedback loop should also be discussed here. It is a well-known
situation when feedback stabilizes the photoelectron flux but degrades the
noise characteristics of light that produce this flux [15, 16, 17]. In the
mentioned case, the direct connection between the operators of the light’s
quadratures and the photocurrent’s operator is lost. There is no such problem
in our case since the feedback controls not the quantum system but the
classical one.

Finally, the third factor is the experimental selection of detectors with the
closest possible characteristics. The selection of suitable photodiodes is an
essential factor in improving the performance of the circuit, and we suggest
that it is this block of the circuit that define cut-of frequency of the
spectral characteristics of the device as a whole.

## References

  * [1] M. Herrero-Collantes, J. C. Garcia-Escartin, Rev. Mod. Phys. 89, 015004 (2017), DOI: 10.1103/RevMOdPhys.89.015004
  * [2] A. V. Gleim, V. V. Chistyakov, O. I. Bannik, J. of Opt. Tech., 84 (6), 362 (2017). DOI: 10.1364/JOT.84.000362
  * [3] Y. Liu, Q. Zhao, M. H. Li, Nature 562, 548551 (2018). DOI: 10.1038/s41586-018-0559-3
  * [4] C. Gabriel, C. Wittmann, D. Sych, Nature Photon 4, 711715 (2010). DOI: 10.1038/nphoton.2010.197
  * [5] T. Symul, S. M. Assad, P. K. Lam, Appl/ Phys. Lett., 98, 231103 (2011). DOI: 10.1063/1.3597793
  * [6] T. Gehring, C. Lupo, A. Kordts, A. et al. Nat. Comm. 12, 605 (2021). DOI: 10.1038/s41467-020-20813-w
  * [7] H. Zhou, P. Zeng, M. Razavi, X. Ma, Phys. Rev. A, 98 (4) 042321 (2018). DOI: 10.1103/PhysRevA.98.042321
  * [8] J. Y. Haw, S. M. Assad, A. M. Lance, N. H. Y. Ng, V. Sharma, P. K. Lam, T. Symul, Phis. Rev. Appl., 3, 054004 (2015). DOI: 10.1103/PhysRevApplied.3.054004
  * [9] B. Xu, Z. Chen, Z. Li, J. Yang, Q. Su, W. Huang, Y. Zhang, H. Guo, Quant. Sci. and Tech., 4 (2), 025013 (2019). DOI: 10.1088/2058-9565/ab0fd9
  * [10] L. Huang, H. Zhou, JOSA B, 36 (3), B130 (2019).DOI:10.1364/JOSAB.36.00B130
  * [11] M. Izutsu, Y. Nakai, and T. Sueta, Opt. Lett. 7, 136-138 (1982). DOI: 10.1364/OL.7.000136
  * [12] O. Alibart, V. D’Auria, M. De Micheli, F. Doutre, F. Kaiser, L. Labonte, T. Lunghi, E. Picholle, and S. Tanzilli, J. Opt. 18, 104001 (2016), DOI: 10.1088/2040-8978/18/10/104001
  * [13] A. Petrov, A. Tronev, P. Agruzov, A. Shamrai, V. Sorotsky, Electronics. 9(11), 1861 (2020). DOI: 10.3390/electronics9111861
  * [14] S. M. Barnett,J. Jeffers, A. Gatti and R. Loudon, Physical Review A, 57(3), 2134 (1998). DOI: 10.1103/PhysRevA.57.2134
  * [15] T. Golubeva, Yu. Golubev and D. Ivanov, Physical Review A, 75(2), 023815 (2007). DOI: 10.1103/PhysRevA.75.023815
  * [16] A. Masalov, A. Putilin and M. Vasilyev, Journal of Modern Optics, 41(10), 1941-1953 (1994). DOI: 10.1080/09500349414551841
  * [17] H. Wiseman and G. Milburn, Physical Review A, 49(2), 1350 (1994). DOI: 10.1103/PhysRevA.49.1350


$S\coloneqq\mathcal{A}_{z_{1}}\cap\mathcal{A}_{z_{2}}\cap\mathcal{A}_{z_{3}}\cap\mathcal{A}_{z_{4}}$
and for every $u\in{[k]\choose 2}\setminus{[4]\choose 2}$ let
$S_{u}\coloneqq\big{\\{}y\in\\{0,1\\}^{{[n]\choose 2}\setminus{[k]\choose
2}}:u\cup y\in S\big{\\}}$ denote the section of $S$ at $u$. Notice that, by
the choice of $\gamma(\mathcal{A})$ in (9.2), we have
$\mathbf{P}(S)=\gamma(\mathcal{A})$ where $\mathbf{P}$ is the uniform
probability measure on $\\{0,1\\}^{{[n]\choose 2}\setminus{[4]\choose 2}}$.
Taking into account this observation, the isomorphic invariance of
$\mathcal{A}$ and proceeding131313Again we point out that here we view
$\\{0,1\\}^{{[n]\choose 2}\setminus{[4]\choose 2}}$ as a discrete probability
space equipped with $\mathbf{P}$. We also note that in this case the
filtration is slightly different since we are working with the index-set
${[n]\choose 2}\setminus{[4]\choose 2}$ instead of ${[n]\choose 2}$. We will
use a similar variation in the next subsection. as in the proof of Theorem
2.3, we obtain that

(9.13)
$\big{\|}\mathbb{E}[\mathbf{1}_{S}\,|\,\mathcal{G}]-\gamma(\mathcal{A})\big{\|}_{L_{2}}^{2}\leqslant\delta$

where $\mathcal{G}$ stands for the $\sigma$-algebra of $\\{0,1\\}^{{[n]\choose
2}\setminus{[4]\choose 2}}$ generated by the partition

(9.14) $\Big{\\{}\big{\\{}z\in\\{0,1\\}^{{[n]\choose 2}\setminus{[4]\choose
2}}:z\upharpoonright{[k]\choose 2}{{\setminus}}{[4]\choose
2}=u\big{\\}}:u\in\\{0,1\\}^{{[k]\choose 2}\setminus{[4]\choose 2}}\Big{\\}}.$

By (9.3), (9.13) and Chebyshev’s inequality, we have

(9.15) $\mu_{3}\big{(}u\in\\{0,1\\}^{{[k]\choose 2}\setminus{[4]\choose
2}}:|\mu_{2}(S_{u})-\gamma(\mathcal{A})|\geqslant\varepsilon\big{)}\leqslant
2^{-\frac{k^{2}}{2}}<2^{-{[k]\choose 2}+{[4]\choose 2}}$

where $\mu_{3}$ denotes the uniform probability measure on
$\\{0,1\\}^{{[k]\choose 2}\setminus{[4]\choose 2}}$ and, as above, $\mu_{2}$
is the uniform probability measure on $\\{0,1\\}^{{[n]\choose
2}\setminus{[k]\choose 2}}$; thus, for every $u\in\\{0,1\\}^{{[k]\choose
2}\setminus{[4]\choose 2}}$,

(9.16) $|\mu_{2}(S_{u})-\gamma(\mathcal{A})|<\varepsilon.$

Let $u_{0}\in\\{0,1\\}^{{[k]\choose 2}\setminus{[4]\choose 2}}$ be such that
$u_{0}^{-1}(\\{1\\})=\emptyset$. Then, by the definitions of $S$ and
$\delta_{4}$ and the isomorphic invariance of $\mathcal{A}$, we see that
$\mu_{2}(S_{u_{0}})=\delta_{4}$ and consequently, by (9.12) and (9.16), we
conclude that

(9.17)
$\gamma(\mathcal{A})\geqslant\mu(\mathcal{A})^{4}-9\varepsilon-\frac{3}{k-3}\geqslant\mu(\mathcal{A})^{4}-\frac{21}{k}\stackrel{{\scriptstyle\eqref{e9.3}}}{{\geqslant}}\mu(\mathcal{A})^{4}-\frac{21}{\sqrt{\log_{2}(\sqrt{n})}}.\qed$

####  9.2. Proof of Theorem 1.8

The main goal of the proof is to extract out of the quasirandom family
$\mathcal{A}$ a boolean two-dimensional approximately spreadable random array
$\bm{X}$ which satisfies the box independence condition; once this is done,
the proof will be completed by an application of Theorem 1.5.

#####  9.2.1. Preliminary tools

We start with a more precise, quantitative, version of Proposition 1.3 for
boolean two-dimensional random arrays. Specifically, let $\ell,m,r\geqslant 2$
be integers with $\ell\leqslant m$, and recall that the multicolor hypergraph
Ramsey number $R_{\ell}(m,r)$ is the least integer $N\geqslant m$ such that
for every set $X$ with $|X|\geqslant N$ and every coloring
$c\colon{X\choose\ell}\to[r]$ there exists $Y\in{X\choose m}$ such that $c$ is
constant on ${Y\choose\ell}$. It is a classical result due to Erdős and Rado
[ER52] that the numbers $R_{\ell}(m,r)$ have (at most) a tower-type dependence
with respect to the parameters $\ell,m,r$. The following fact is the promised
quantitative version of Proposition 1.3; the proof follows by invoking the
relevant definitions, and it is left to the reader.

######  Fact 9.2.

Let $0<\eta\leqslant 1$, let $\ell\geqslant 2$ be an integer, and let $N$ be
an integer such that

(9.18) $N\geqslant R_{\ell}\Big{(}2\ell,\big{(}2^{{\ell\choose
2}}\left\lceil\eta^{-1}\right\rceil\big{)}^{{\ell\choose 2}}\Big{)}.$

Then for every boolean two-dimensional random array $\bm{X}$ on $[N]$ there
exists $L\in{[N]\choose\ell}$ such that the subarray $\bm{X}_{L}$ is
$\eta$-spreadable. $($See Definition _1.1_.$)$

We proceed by introducing some terminology and some pieces of notation. Let
$m\geqslant\ell$ be positive integers and let $F\in{[m]\choose\ell}$; given
two subsets $L\subseteq M$ of $\mathbb{N}$ with $|L|=\ell$ and $|M|=m$, we say
that the _relative position of $L$ inside $M$ is $F$_ if, denoting by
$\\{i_{1}<\cdots<i_{m}\\}$ the increasing enumeration of $M$, we have that
$L=\\{i_{j}:j\in F\\}$.

Moreover, for every finite subset $M$ of $\mathbb{N}$ with $|M|\geqslant 2$
every $e\in{M\choose 2}$ we shall denote by $x(e,M)\in\\{0,1\\}^{{M\choose
2}}$ the unique element satisfying $x(e,M)^{-1}(\\{1\\})=\\{e\\}$.

It is also convenient to introduce the following definition. (Recall that for
every integer $n\geqslant 2$ by $\mu$ we denote the uniform probability
measure on $\\{0,1\\}^{{[n]\choose 2}}$.)

######  Definition 9.3 (Admissibility).

Let $0<\eta\leqslant 1$, let $n\geqslant m\geqslant\ell\geqslant 2$ be
integers, let $\mathcal{A}\subseteq\\{0,1\\}^{{[n]\choose 2}}$ and let
$F\in{[m]\choose\ell}$. Given $P\subseteq[n]$ with $|P|\geqslant m$, we say
that $P$ is _$(\mathcal{A},\eta,F)$ -admissible_ if for every $M\in{P\choose
m}$, denoting by $\nu$ the uniform probability measure on
$\\{0,1\\}^{{[n]\choose 2}\setminus{M\choose 2}}$, the following hold.

  1. ($\mathcal{P}$1)

For every $x\in\\{0,1\\}^{{M\choose 2}}$ we have
$|\nu(\mathcal{A}_{x})-\mu(\mathcal{A})|\leqslant\eta$ where $\mathcal{A}_{x}$
is the section of $\mathcal{A}$ at $x$.

  2. ($\mathcal{P}$2)

If $L\in{M\choose\ell}$ is the unique subset of $M$ whose relative position
inside $M$ is $F$, then the two-dimensional random array
$\langle\mathbf{1}_{\mathcal{A}_{x(e,M)}}:e\in{L\choose 2}\rangle$ is
$\eta$-spreadable. $($Here, we view $\\{0,1\\}^{{[n]\choose
2}\setminus{M\choose 2}}$ as a discrete probability space equipped with $\nu$
and we denote by $\mathcal{A}_{x(e,M)}$ the section of $\mathcal{A}$ at
$x(e,M)$.$)$

We have the following lemma.

######  Lemma 9.4.

Let $0<\eta\leqslant 1$, let $\ell\geqslant 2$ be an integer, and set

(9.19) $m=m(\eta,\ell)\coloneqq R_{\ell}\Big{(}2\ell,\big{(}2^{{\ell\choose
2}}\left\lceil\eta^{-1}\right\rceil\big{)}^{{\ell\choose 2}}\Big{)}.$

Then for every integer $p\geqslant m$ there exists an integer $q\geqslant p$
with the following property. If $n\geqslant q$ is an integer and
$\mathcal{A}\subseteq\\{0,1\\}^{{[n]\choose 2}}$ is a family of graphs, then
for every $Q\in{[n]\choose q}$ there exist $F\in{[m]\choose\ell}$ and
$P\in{Q\choose p}$ such that $P$ is $(\mathcal{A},\eta,F)$-admissible.

###### Proof.

Fix $p\geqslant m$ and set

(9.20) $q_{1}\coloneqq R_{\ell}\Big{(}p,{m\choose\ell}\Big{)}\ \ \text{ and }\
\
q\coloneqq\max\big{\\{}\left\lceil\eta^{-2}\right\rceil,2^{q_{1}^{2}}\big{\\}}\cdot
q_{1}$

We claim that $q$ is as desired. Indeed, let $n,\mathcal{A}$ be as in the
statement of the lemma, and let $Q\in{[n]\choose q}$ be arbitrary. Setting
$\delta\coloneqq\max\big{\\{}\eta^{2},2^{-q_{1}^{2}}\big{\\}}$ and
arguing141414Note that, although here we proceed exactly as in (9.4), we
cannot guarantee that the set $Q_{1}$ is an initial interval of $Q$ since the
family $\mathcal{A}$ is not necessarily isomorphic invariant. as in Theorem
2.3, we select $Q_{1}\in{Q\choose q_{1}}$ such that

(9.21)
$\big{\|}\mathbb{E}[\mathbf{1}_{\mathcal{A}}\,|\,\mathcal{F}]-\mu(\mathcal{A})\big{\|}^{2}_{L_{2}}\leqslant\delta$

where $\mathcal{F}$ denotes the $\sigma$-algebra of $\\{0,1\\}^{{[n]\choose
2}}$ generated by the partition

(9.22) $\Big{\\{}\big{\\{}z\in\\{0,1\\}^{[n]\choose
2}:z\upharpoonright{Q_{1}\choose 2}=x\big{\\}}:x\in\\{0,1\\}^{Q_{1}\choose
2}\Big{\\}}.$

(Recall that we view $\\{0,1\\}^{[n]\choose 2}$ as a discrete probability
space equipped with $\mu$.) Since $\sqrt{\delta}<2^{-{q_{1}\choose 2}}$, by
(9.21) and Chebyshev’s inequality, for every $x\in\\{0,1\\}^{Q_{1}\choose 2}$
we have

(9.23) $|\mu_{1}(\mathcal{A}_{x})-\mu(\mathcal{A})|\leqslant\eta$

where $\mu_{1}$ denotes the uniform probability measure on
$\\{0,1\\}^{{[n]\choose 2}\setminus{Q_{1}\choose 2}}$ and, as usual,
$\mathcal{A}_{x}$ is the section of $\mathcal{A}$ at $x$. By double averaging,
this yields that for every $M\in{Q_{1}\choose m}$ and every
$x\in\\{0,1\\}^{{M\choose 2}}$ we have
$|\nu(\mathcal{A}_{x})-\mu(\mathcal{A})|\leqslant\eta$ where $\nu$ is the
uniform probability measure on $\\{0,1\\}^{{[n]\choose 2}\setminus{M\choose
2}}$. In other words, property ($\mathcal{P}$1) in Definition 9.3 will be
satisfied as long as the desired set $P$ is contained in $Q_{1}$.

For property ($\mathcal{P}$2) we argue as follows. Let $M\in{Q_{1}\choose m}$
be arbitrary; by the choice of the constant $m$ in (9.19) and Fact 9.2 applied
to the boolean, two-dimensional random array
$\langle\mathbf{1}_{\mathcal{A}_{x(e,M)}}:e\in{M\choose 2}\rangle$, there
exists $F_{M}\in{[m]\choose\ell}$ such that if $L\in{M\choose\ell}$ is the
unique subset of $M$ whose relative position inside $M$ is $F_{M}$, then the
random array $\langle\mathbf{1}_{\mathcal{A}_{x(e,M)}}:e\in{L\choose
2}\rangle$ is $\eta$-spreadable. By the choice of $q_{1}$ in (9.20) and
another application of Ramsey’s theorem, there exist $P\in{Q_{1}\choose p}$
and $F\in{[m]\choose\ell}$ such that $F_{M}=F$ for every $M\in{P\choose m}$.
That is, property ($\mathcal{P}$2) is satisfied for $P$, as desired. ∎

#####  9.2.2. Numerical parameters

Our next step is to introduce some numerical parameters. We fix
$0<\delta\leqslant 1$ and an integer $k\geqslant 2$, and we begin by selecting
$0<\eta,\theta_{0}\leqslant 1$ and an integer $\ell\geqslant 4k$ such that

(9.24)
$\eta+\Big{(}\lfloor\ell/k\rfloor^{-1}+2k^{2}\eta+800k^{2}\big{(}\ell^{-1/16}+\eta^{1/16}+(10\eta+\theta_{0})^{1/16}\big{)}\Big{)}^{1/2}<\delta^{{k\choose
2}+1}.$

Next we set

(9.25) $\displaystyle m\coloneqq
m(\eta,\ell)\stackrel{{\scriptstyle\eqref{e9.19}}}{{=}}R_{\ell}\Big{(}2\ell,\big{(}2^{{\ell\choose
2}}\left\lceil\eta^{-1}\right\rceil\big{)}^{{\ell\choose 2}}\Big{)}$ (9.26)
$\displaystyle\varrho\coloneqq\eta^{2}2^{-m^{2}}$ (9.27) $\displaystyle
p\coloneqq 5m\lceil\varrho^{-1}\rceil+4$ (9.28) $\displaystyle
q_{1}\coloneqq\mathrm{R}_{m}\Big{(}p,{m\choose\ell}\Big{)}.$

Finally, we define

(9.29)
$q_{0}\coloneqq\max\big{\\{}\lceil\eta^{2}\rceil,2^{q_{1}^{2}}\big{\\}}\cdot
q_{1}\ \ \text{ and }\ \
\theta\coloneqq\frac{1}{2}\cdot\min\Big{\\{}\theta_{0},{q_{0}\choose
4}^{-1}\Big{\\}}.$

Notice, in particular, that with this choice we also have that

(9.30)
$\eta+\Big{(}\lfloor\ell/k\rfloor^{-1}+2k^{2}\eta+800k^{2}\big{(}\ell^{-1/16}+\eta^{1/16}+(10\eta+\theta)^{1/16}\big{)}\Big{)}^{1/2}<\delta^{{k\choose
2}+1}.$

#####  9.2.3. Completion of the proof

We are ready for the main part of the argument. As above, let
$0<\delta\leqslant 1$ and $k\geqslant 2$. Also let $n\geqslant q_{0}$ be an
integer and let $\mathcal{A}\subseteq\\{0,1\\}^{[n]\choose 2}$ be a
$\theta$-quasirandom family of graphs with $\mu(\mathcal{A})\geqslant\delta$,
where $q_{0},\theta$ are as in (9.29).

By Lemma 9.4, for every $Q\in{[n]\choose q_{0}}$ we fix $P_{Q}\in{Q\choose p}$
and $F_{Q}\in{[m]\choose\ell}$ such that $P_{Q}$ is
$(\mathcal{A},\eta,F_{Q})$-admissible in the sense of Definition 9.3.
Moreover, denoting by $\\{r_{1}<\dots<r_{p}\\}$ the increasing enumeration of
$P_{Q}$, we set $U_{Q}\coloneqq\big{\\{}r_{jm\lceil
1/\varrho\rceil+j}:j\in\\{1,2,3,4\\}\big{\\}}\in{Q\choose 4}$. Then observe
that

(9.31) $\Big{|}\Big{\\{}U_{Q}:Q\in{[n]\choose
q_{0}}\Big{\\}}\Big{|}\geqslant{n\choose 4}\,{q_{0}\choose 4}^{-1}.$

Since the family $\mathcal{A}$ is $\theta$-quasirandom, by Definition 1.7 and
the choice of $\theta$ in (9.29), there exists $Q_{0}\in{[n]\choose q_{0}}$
such that, writing $U_{Q_{0}}=\\{u_{1}<u_{2}<u_{3}<u_{4}\\}$ and
setting151515Recall that by $x(\\{u_{1},u_{3}\\},U_{Q_{0}})$ we denote the
unique element of $\\{0,1\\}^{{Q_{0}\choose 2}}$ such that
$x(\\{u_{1},u_{3}\\},U_{Q_{0}})^{-1}(\\{1\\})=\\{u_{1},u_{3}\\}$, and
similarly for $x(\\{u_{1},u_{4}\\},U_{Q_{0}})$,
$x(\\{u_{2},u_{3}\\},U_{Q_{0}})$, $x(\\{u_{2},u_{4}\\},U_{Q_{0}})$.
$B\coloneqq\mathcal{A}_{x(\\{u_{1},u_{3}\\},U_{Q_{0}})}\cap\mathcal{A}_{x(\\{u_{1},u_{4}\\},U_{Q_{0}})}\cap\mathcal{A}_{x(\\{u_{2},u_{3}\\},U_{Q_{0}})}\cap\mathcal{A}_{x(\\{u_{2},u_{4}\\},U_{Q_{0}})}$,
we have

(9.32) $\mathbf{P}(B)\leqslant\mu(\mathcal{A})^{4}+\theta$

where $\mathbf{P}$ denotes the uniform probability measure on
$\\{0,1\\}^{{[n]\choose 2}\setminus{U_{Q_{0}}\choose 2}}$.

As above, let $\\{r_{1}<\dots<r_{p}\\}$ denote the increasing enumeration of
the set $P_{Q_{0}}$. For every
$i\in\big{\\{}1,\dots,\lceil\varrho^{-1}\rceil\big{\\}}$ set

(9.33) $R_{i}\coloneqq\\{r_{j+(t-1)(m\lceil 1/\varrho\rceil+1)}:t\in[5]\text{
and }j\in[im]\big{\\}}$

and notice that $R_{i}\cap U_{Q_{0}}=\emptyset$; also let $\mathcal{F}_{i}$ be
the $\sigma$-algebra of $\\{0,1\\}^{{[n]\choose 2}\setminus{U_{Q_{0}}\choose
2}}$ generated by the partition

$\Big{\\{}\big{\\{}y\in\\{0,1\\}^{{[n]\choose 2}\setminus{U_{Q_{0}}\choose
2}}:y\upharpoonright{R_{i}\cup U_{Q_{0}}\choose 2}\setminus{U_{Q_{0}}\choose
2}=z\big{\\}}:z\in\\{0,1\\}^{{R_{i}\cup U_{Q_{0}}\choose
2}\setminus{U_{Q_{0}}\choose 2}}\Big{\\}}.$

Finally, set

(9.34) $R_{0}\coloneqq\emptyset\ \ \text{ and }\ \
\mathcal{F}_{0}\coloneqq\Big{\\{}\emptyset,\\{0,1\\}^{{[n]\choose
2}\setminus{U_{Q_{0}}\choose 2}}\Big{\\}}.$

Figure 5. The $\sigma$-algebra $\mathcal{F}_{i}$ associated with the set
$R_{i}$.

Consider the Doob martingale for $\mathbf{1}_{B}$ with respect to the
filtration
$\mathcal{F}_{0},\mathcal{F}_{1},\dots,\mathcal{F}_{\lceil\varrho^{-1}\rceil}$;
using the elementary fact that martingale difference sequences are orthogonal
in $L_{2}$, we may select
$i_{0}\in\big{\\{}1,\dots,\lceil\varrho^{-1}\rceil\big{\\}}$ such that

(9.35)
$\big{\|}\mathbb{E}[\mathbf{1}_{B}\,|\,\mathcal{F}_{i_{0}}]-\mathbb{E}[\mathbf{1}_{B}\,|\,\mathcal{F}_{i_{0}-1}]\big{\|}_{L_{2}}^{2}\leqslant\varrho.$

(Here, we view $\\{0,1\\}^{{[n]\choose 2}\setminus{U_{Q_{0}}\choose 2}}$ as a
discrete probability space equipped with $\mathbf{P}$.) Next, we select
$M\in{U_{Q_{0}}\cup(R_{i_{0}}\setminus R_{i_{0}-1})\choose
m}\subseteq{P_{Q_{0}}\choose m}$ such that, denoting by $L$ the unique element
of ${M\choose\ell}$ whose relative position inside $M$ is $F_{Q_{0}}$, we have
that $U_{Q_{0}}\subseteq L$; this selection is possible by the choice of
$R_{i_{0}}$ in (9.33). Finally, denote by $\mathcal{F}$ the $\sigma$-algebra
of $\\{0,1\\}^{{[n]\choose 2}\setminus{U_{Q_{0}}\choose 2}}$ generated by the
partition

$\Big{\\{}\big{\\{}y\in\\{0,1\\}^{{[n]\choose 2}\setminus{U_{Q_{0}}\choose
2}}:y\upharpoonright{M\choose 2}\setminus{U_{Q_{0}}\choose
2}=z\big{\\}}:z\in\\{0,1\\}^{{M\choose 2}\setminus{U_{Q_{0}}\choose
2}}\Big{\\}}$

and observe that $\mathcal{F}$ is a sub-$\sigma$-algebra of
$\mathcal{F}_{i_{0}}$, while the $\sigma$-algebras $\mathcal{F}$ and
$\mathcal{F}_{i_{0}-1}$ are independent. Therefore, by (9.35) and the fact
that the conditional expectation is a linear contraction on $L_{2}$, we see
that

(9.36)
$\big{\|}\mathbb{E}[\mathbf{1}_{B}\,|\,\mathcal{F}]-\mathbf{P}(B)\big{\|}_{L_{2}}^{2}\leqslant\varrho.$

As we have already noted, this estimate together with Chebyshev’s inequality
and the choice of $\varrho$ in (9.26) yield that for every
$z\in\\{0,1\\}^{{M\choose 2}\setminus{U_{Q_{0}}\choose 2}}$ we have

(9.37) $|\nu(B_{z})-\mathbf{P}(B)|\leqslant\eta$

where $\nu$ is the uniform probability measure on $\\{0,1\\}^{{[n]\choose
2}\setminus{M\choose 2}}$ and $B_{z}$ is the section of $B$ at $z$.

Now let $z_{0}\in\\{0,1\\}^{{M\choose 2}\setminus{U_{Q_{0}}\choose 2}}$ be
such that $z_{0}^{-1}(\\{1\\})=\emptyset$. By (9.32) and (9.37), we have

(9.38) $\nu(B_{z_{0}})\leqslant\mu(\mathcal{A})^{4}+\eta+\theta.$

Also notice that
$B_{z_{0}}=\mathcal{A}_{x(\\{u_{1},u_{3}\\},M)}\cap\mathcal{A}_{x(\\{u_{1},u_{4}\\},M)}\cap\mathcal{A}_{x(\\{u_{2},u_{3}\\},M)}\cap\mathcal{A}_{x(\\{u_{2},u_{4}\\},M)}$.
On the other hand, recall that $P_{Q_{0}}$ is
$(\mathcal{A},\eta,F_{Q_{0}})$-admissible and that $L$ is the unique subset of
$M\in{P_{Q_{0}}\choose m}$ whose relative position inside $M$ is $F_{Q_{0}}$.
Taking into account these observations and using properties ($\mathcal{P}$1)
and ($\mathcal{P}$2) in Definition 9.3, we see that the boolean random array
$\langle\mathbf{1}_{\mathcal{A}_{x(e,M)}}:e\in{L\choose 2}\rangle$ is
$\eta$-stationary and it satisfies (1.7) with $\vartheta=10\eta+\theta$. Let
$\\{s_{1}<\dots<s_{m}\\}$ denote the increasing enumeration of $M$, and for
every $j\in\big{\\{}1,\dots,\lfloor\ell/k\rfloor\big{\\}}$ set

(9.39) $K_{j}\coloneqq\big{\\{}s_{i}:i\in[jk]\setminus[(j-1)k]\big{\\}}\ \
\text{ and }\ \ \Gamma_{j}\coloneqq\bigcap_{e\in{K_{j}\choose
2}}\mathcal{A}_{x(e,M)}.$

By Theorem 1.5, property ($\mathcal{P}$1) in Definition 9.3 and the previous
discussion, for every $j,l\in\big{\\{}1,\dots,\lfloor\ell/k\rfloor\big{\\}}$
with $j\neq l$ we have

(9.40) $\big{|}\nu(\Gamma_{j})-\mu(\mathcal{A})^{k\choose
2}\big{|}\leqslant\eta{k\choose 2}+400{k\choose
2}\big{(}\ell^{-1/16}+\eta^{1/16}+(10\eta+\theta)^{1/16}\big{)}$

and

(9.41) $\big{|}\nu(\Gamma_{j}\cap\Gamma_{l})-\mu(\mathcal{A})^{2{k\choose
2}}\big{|}\leqslant\eta\,2{k\choose 2}+400\cdot 2{k\choose
2}\big{(}\ell^{-1/16}+\eta^{1/16}+(10\eta+\theta)^{1/16}\big{)}.$

Introduce the random variable

(9.42)
$X\coloneqq\frac{1}{\lfloor\ell/k\rfloor}\sum_{j=1}^{\lfloor\ell/k\rfloor}\mathbf{1}_{\Gamma_{j}}$

and observe that, by (9.40) and (9.41), we have

(9.43) $\|X-\mu(\mathcal{A})^{k\choose
2}\|_{L_{2}}\leqslant\Big{(}\lfloor\ell/k\rfloor^{-1}+2k^{2}\eta+800k^{2}\big{(}\ell^{-1/16}+\eta^{1/16}+(30\eta+6\theta)^{1/16}\big{)}\Big{)}^{1/2}.$

Let $x_{0}\in\\{0,1\\}^{M\choose 2}$ be the unique element satisfying
$x_{0}^{-1}(\\{1\\})=\emptyset$ and note that

(9.44)
$\displaystyle\mathbb{E}[X\mathbf{1}_{\mathcal{A}_{x_{0}}}]\geqslant\mu(\mathcal{A})^{k\choose
2}\nu(\mathcal{A}_{x_{0}})-\sqrt{\nu(\mathcal{A}_{x_{0}})}\,\|X-\mu(\mathcal{A})^{k\choose
2}\|_{L_{2}}$
$\displaystyle\stackrel{{\scriptstyle(\hyperref@@ii[9P1]{\mathcal{P}1}),\eqref{e9.43}}}{{\geqslant}}$
$\displaystyle\delta^{{k\choose
2}+1}-\eta-\Big{(}\lfloor\ell/k\rfloor^{-1}+2k^{2}\eta+800k^{2}\big{(}\ell^{-1/16}+\eta^{1/16}+(10\eta+\theta)^{1/16}\big{)}\Big{)}^{1/2}.$

Therefore, by (9.30), we have
$\mathbb{E}[X\mathbf{1}_{\mathcal{A}_{x_{0}}}]>0$ which in turn implies that
there exists $j_{0}\in\big{\\{}1,\dots,\lfloor\ell/k\rfloor\big{\\}}$ such
that $\mathcal{A}_{x_{0}}\cap\Gamma_{j_{0}}\neq\emptyset$. By the choices of
$\Gamma_{j_{0}}$ in (9.39) and $x_{0}$, it is clear that the set
$K_{j_{0}}\in{[n]\choose k}$ is as desired. The proof of Theorem 1.8 is
completed.

######  Remark 9.5 (Analysis of the bounds).

Using the Erdős–Rado theorem [ER52], it is not hard to see that the proof of
Theorem 1.8 yields a tower-type dependence of $\theta$ and $\ell_{0}$ with
respect to the parameters $\delta$ and $k$. More precisely, there exists a
primitive recursive $\psi\colon\mathbb{N}\times\mathbb{N}\to\mathbb{N}$
function belonging to the class $\mathcal{E}^{4}$ of Grzegorczyk’s
hierarchy161616See [DK16, Appendix A] for an introduction to Grzegorczyk’s
hierarchy and a discussion of its role in analyzing bounds in Ramsey theory.
such that
$\theta^{-1},\ell_{0}\leqslant\psi\big{(}\left\lceil\delta^{-1}\right\rceil,k\big{)}$
for every $0<\delta\leqslant 1$ and every integer $k\geqslant 2$.

######  Remark 9.6 (Extensions to families of uniform hypergraphs).

Theorem 1.8 can be extended to families of $d$-uniform hypergraphs
$\mathcal{A}\subseteq\\{0,1\\}^{{[n]\choose d}}$ for any integer $d\geqslant
2$; this can be done by using Theorem 3.2 instead Theorem 1.5 and
appropriately modifying the notion of quasirandomness in Definition 1.7. We
leave the (fairly straightforward) formulations of these extensions to the
interested reader.

######  Remark 9.7.

Let $\mathcal{A}\subseteq\\{0,1\\}^{{[n]\choose 2}}$ be a family of graphs on
$[n]$, let $K\subseteq[n]$ with $|K|\geqslant 2$, and let
$\mathcal{S}\subseteq\\{0,1\\}^{{K\choose 2}}$ be a family of graphs on $K$.
We say that $\mathcal{A}$ _smashes_ $\mathcal{S}$ if there exists
$W\subseteq{[n]\choose 2}\setminus{K\choose 2}$ such that $W\cup
H\in\mathcal{A}$ for every $H\in\mathcal{S}$. With this terminology, Theorem
1.8 is equivalent to saying that if the family $\mathcal{A}$ is dense and
quasirandom—in the sense of Definition 1.7—then it smashes all graphs with at
most one edge on some $K\in{[n]\choose k}$. It would be interesting to find
quasirandomness conditions which ensure that the family $\mathcal{A}$ smashes
richer families of small graphs. In this direction, the following problem is
the most intriguing.

######  Problem 9.8.

Find natural quasirandomness conditions on a family of graphs $\mathcal{A}$
which ensure that $\mathcal{A}$ smashes _all_ graphs on some $K\in{[n]\choose
k}$.

###  Appendix A Examples

Our goal in this appendix is to present examples which show that the box
independence condition in Theorems 1.4 and 6.1 is essentially optimal. We
focus on boolean random arrays as this case already covers all underlying
phenomena.

####  A.1. Boxes and faces

We start by introducing some terminology which will be used throughout this
section. Let $d\geqslant 2$ be an integer; we say that a subset $B$ of
${\mathbb{N}\choose d}$ is a _$d$ -dimensional box of $\mathbb{N}$_ if it is a
$d$-dimensional box of $[n]$ for some integer $n\geqslant 2d$. (See Subsection
3.1.) Moreover, we say that a subset $F$ of ${\mathbb{N}\choose d}$ is a
_$(d-1)$ -face of $\mathbb{N}$_ if it is of the form
$\mathrm{Box}(\mathcal{H})$ where $\mathcal{H}=(H_{1},\dots,H_{d})$ is a
finite sequence of nonempty subsets of $\mathbb{N}$ of cardinality at most $2$
with $\max(H_{i})<\min(H_{i+1})$ for all $i\in[d-1]$, and such that
$\sum_{i=1}^{d}|H_{i}|=2d-1$. (Thus, $|H_{i}|=2$ for all but at one
$i\in[d]$.)

####  A.2. The two-dimensional case

We have the following proposition.

######  Proposition A.1.

There exists a boolean, exchangeable, two-dimensional random array
$\bm{X}=\langle X_{s}:s\in{\mathbb{N}\choose 2}\rangle$ on $\mathbb{N}$ with
the following properties.

  1. ($\mathcal{P}$1)

For every $s\in{\mathbb{N}\choose 2}$ we have $\mathbb{E}[X_{s}]=\frac{1}{2}$.

  2. ($\mathcal{P}$2)

For every distinct $s,t\in{\mathbb{N}\choose 2}$ we have
$\mathbb{E}[X_{s}X_{t}]=\frac{1}{4}$.

  3. ($\mathcal{P}$3)

For every $2$-dimensional box $B$ of $\mathbb{N}$ and every nonempty subset
$G$ of $B$ with $G\neq B$ we have $\mathbb{E}\big{[}\prod_{s\in
G}X_{s}\big{]}=(\frac{1}{2})^{|G|}$.

  4. ($\mathcal{P}$4)

For every $2$-dimensional box $B$ of $\mathbb{N}$ we have
$\mathbb{E}\big{[}\prod_{s\in B}X_{s}\big{]}=\frac{3}{2}(\frac{1}{2})^{4}$.

  5. ($\mathcal{P}$5)

Let $n\geqslant 8$ be an integer, and let $\bm{X}_{n}$ denote the subarray of
$\bm{X}$ determined by $[n]$. $($See Definition _1.1_.$)$ Then there exists a
translated multilinear polynomial $f\colon\mathbb{R}^{{[n]\choose
2}}\to\mathbb{R}$ of degree $4$ with $\mathbb{E}[f(\bm{X}_{n})]=0$ and
$\|f(\bm{X}_{n})\|_{L_{\infty}}\leqslant 1$, such that for every subset $I$ of
$[n]$ with $|I|\geqslant 8$ we have
$\mathbb{P}\big{(}\big{|}\mathbb{E}[f(\bm{X}_{n})\,|\,\mathcal{F}_{I}]\big{|}\geqslant
2^{-11}\big{)}\geqslant 2^{-11}$.

###### Proof.

We will define the random array $\bm{X}$ by providing an integral
representation of its distribution. (Of course, this maneuver is expected by
the Aldous–Hoover representation theorem [Ald81, Hoo79].) Specifically, set
$V\coloneqq\\{0,1\\}$ and $A\coloneqq\\{(0,0),(1,1)\\}\subseteq V^{2}$; we
view $V$ as a discrete probability space equipped with the uniform probability
measure. We also set $\Omega\coloneqq\\{0,1\\}^{\mathbb{N}\choose 2}$ and we
equip $\Omega$ with the product $\sigma$-algebra which we denote by $\Sigma$.
Let $\mathbb{P}$ be the unique probability measure on $(\Omega,\Sigma)$ which
satisfies, for every nonempty finite subset $\mathcal{F}$ of
${\mathbb{N}\choose 2}$, that

(A.1) $\mathbb{P}\Big{(}\big{\\{}(x_{t})_{t\in{\mathbb{N}\choose
2}}\in\Omega:x_{s}=1\text{ for all
}s\in\mathcal{F}\big{\\}}\Big{)}=\frac{1}{2}\Big{(}\frac{1}{2}\Big{)}^{|\mathcal{F}|}+\frac{1}{2}\int\prod_{s\in\mathcal{F}}\mathbf{1}_{A}(\bm{v}_{s})\,d\bm{\mu}(\bm{v})$

where: (i) $\bm{\mu}$ denotes the product measure on $V^{\mathbb{N}}$ obtained
by equipping each factor with the uniform probability measure on $V$, and (ii)
for every $\bm{v}=(v_{i})\in V^{\mathbb{N}}$ and every
$s=\\{i_{1}<i_{2}\\}\in{\mathbb{N}\choose 2}$ by
$\bm{v}_{s}=(v_{i_{1}},v_{i_{2}})\in V^{2}$ we denote the restriction of
$\bm{v}$ on the coordinates determined by $s$. Next, for every
$s\in{\mathbb{N}\choose 2}$ let $X_{s}\colon\Omega\to\\{0,1\\}$ denote the
projection on the $s$-th coordinate, that is,
$X_{s}\big{(}(x_{t})_{t\in{\mathbb{N}\choose 2}}\big{)}=x_{s}$ for every
$(x_{t})_{t\in{\mathbb{N}\choose 2}}\in\Omega$. The fact that the set $A$ is
symmetric implies that the random array $\bm{X}=\langle
X_{s}:s\in{\mathbb{N}\choose 2}\rangle$ is exchangeable; moreover, for every
nonempty finite subset $\mathcal{F}$ of ${\mathbb{N}\choose 2}$ we have

(A.2)
$\mathbb{E}\Big{[}\prod_{s\in\mathcal{F}}X_{s}\Big{]}=\frac{1}{2}\Big{(}\frac{1}{2}\Big{)}^{|\mathcal{F}|}+\frac{1}{2}\int\prod_{s\in\mathcal{F}}\mathbf{1}_{A}(\bm{v}_{s})\,d\bm{\mu}(\bm{v}).$

Using (A.2), properties ($\mathcal{P}$1)–($\mathcal{P}$4) follow from a direct
computation.

In order to verify property ($\mathcal{P}$5) we argue as in the proof of
Proposition 2.8. Fix an integer $n\geqslant 8$. Let $\mathrm{Box}(2)$ be the
$2$-dimensional box of $\mathbb{N}$ defined in (3.2). We define
$f\colon\mathbb{R}^{[n]\choose 2}\to\mathbb{R}$ by setting for every
$\bm{x}=(x_{t})_{t\in{[n]\choose 2}}\in\mathbb{R}^{[n]\choose 2}$

(A.3) $\displaystyle f(\bm{x})$
$\displaystyle\coloneqq\prod_{s\in\mathrm{Box}(2)}\\!\\!x_{s}-\mathbb{E}\Big{[}\prod_{s\in\mathrm{Box}(2)}\\!\\!X_{s}\Big{]}$
$\displaystyle\\!\stackrel{{\scriptstyle\eqref{e3.2}}}{{=}}x_{\\{1,3\\}}x_{\\{1,4\\}}x_{\\{2,3\\}}x_{\\{2,4\\}}-\mathbb{E}[X_{\\{1,3\\}}X_{\\{1,4\\}}X_{\\{2,3\\}}X_{\\{2,4\\}}].$

It is clear that $f$ is a translated multilinear polynomial of degree $4$ with
$\mathbb{E}[f(\bm{X}_{n})]=0$ and $\|f(\bm{X}_{n})\|_{L_{\infty}}\leqslant 1$.
(Recall that $\bm{X}_{n}$ denotes the subarray of $\bm{X}$ determined by
$[n]$.) Let $I$ be an arbitrary subset of $[n]$ with $|I|\geqslant 8$. Since
$|I|\geqslant 8$, there exists a $2$-dimensional box $B$ of $\mathbb{N}$ with
$B\subseteq{I\choose 2}$ and such that $\min(s)\geqslant 5$ for every $s\in
B$. Set $C\coloneqq\bigcap_{s\in B}[X_{s}=1]$ and observe that
$C\in\mathcal{F}_{I}$. Hence, by the exchangeability of $\bm{X}$, we have

(A.4)
$\displaystyle\mathbb{E}\big{[}\mathbb{E}[f(\bm{X}_{n})\,|\,\mathcal{F}_{I}]\,\mathbf{1}_{C}\big{]}$
$\displaystyle=\mathbb{E}[f(\bm{X}_{n})\mathbf{1}_{C}]$
$\displaystyle=\mathbb{E}\Big{[}\prod_{s\in\mathrm{Box}(2)\cup
B}X_{s}\Big{]}-\mathbb{E}\Big{[}\bigcap_{s\in\mathrm{Box}(2)}X_{s}\Big{]}^{2}\stackrel{{\scriptstyle\eqref{ea.2}}}{{=}}\frac{1}{2^{10}}$

which implies that
$\mathbb{P}\big{(}\big{|}\mathbb{E}[f(\bm{X}_{n})\,|\,\mathcal{F}_{I}]\big{|}\geqslant
2^{-11}\big{)}\geqslant 2^{-11}$. The proof is completed. ∎

####  A.3. The higher-dimensional case

The following result is the higher-dimensional analogue of Proposition A.1.

######  Proposition A.2.

Let $d\geqslant 3$ be an integer. Also let $\delta>0$. Then there exists a
boolean, exchangeable, $d$-dimensional random array $\bm{X}=\langle
X_{s}:s\in{\mathbb{N}\choose d}\rangle$ on $\mathbb{N}$ with the following
properties.

  1. ($\mathcal{P}$1)

For every $s\in{\mathbb{N}\choose d}$ we have
$\big{|}\mathbb{E}[X_{s}]-\frac{1}{2}\big{|}\leqslant\delta$.

  2. ($\mathcal{P}$2)

For every distinct $s,t\in{\mathbb{N}\choose d}$ we have
$\big{|}\mathbb{E}[X_{s}X_{t}]-\frac{1}{4}\big{|}\leqslant\delta$.

  3. ($\mathcal{P}$3)

For every $(d-1)$-face $F$ of $\mathbb{N}$ we have
$\big{|}\mathbb{E}\big{[}\prod_{s\in
F}X_{s}\big{]}-(\frac{1}{2})^{|F|}\big{|}\leqslant\delta$.

  4. ($\mathcal{P}$4)

For every $d$-dimensional box $B$ of $\mathbb{N}$ we have
$\big{|}\mathbb{E}\big{[}\prod_{s\in
B}X_{s}\big{]}-\frac{3}{2}(\frac{1}{2})^{|B|}\big{|}\leqslant\delta$.

  5. ($\mathcal{P}$5)

Set $\vartheta\coloneqq 16^{-1}2^{-2^{d+1}}$. $($Note that $\vartheta$ does
not dependent on $\delta$.$)$ Let $n\geqslant 4d$ be an integer, and let
$\bm{X}_{n}$ denote the subarray of $\bm{X}$ determined by $[n]$. Then there
exists a translated multilinear polynomial $f\colon\mathbb{R}^{{[n]\choose
d}}\to\mathbb{R}$ of degree $2^{d}$ with $\mathbb{E}[f(\bm{X}_{n})]=0$ and
$\|f(\bm{X}_{n})\|_{L_{\infty}}\leqslant 1$, such that for every subset $I$ of
$[n]$ with $|I|\geqslant 4d$ we have
$\mathbb{P}\big{(}\big{|}\mathbb{E}[f(\bm{X}_{n})\,|\,\mathcal{F}_{I}]\big{|}\geqslant\vartheta\big{)}\geqslant\vartheta$.

######  Remark A.3.

We point out that property ($\mathcal{P}$3) is rather strong. Indeed, arguing
as in the proof of Theorem 3.2, it is not hard to show that if $\bm{X}=\langle
X_{s}:s\in{\mathbb{N}\choose d}\rangle$ is any boolean, spreadable,
$d$-dimensional random array on $\mathbb{N}$ which satisfies properties
($\mathcal{P}$1) and ($\mathcal{P}$3) of Proposition A.2, then for every
$d$-dimensional box $B$ of $\mathbb{N}$ and every nonempty subset $G$ of $B$
with $G\neq B$ we have

(A.5) $\Big{|}\mathbb{E}\Big{[}\prod_{s\in
G}X_{s}\Big{]}-\Big{(}\frac{1}{2}\Big{)}^{|G|}\Big{|}=o_{\delta\to 0;d}(1).$

Note that (A.5) barely misses to imply that $\bm{X}$ satisfies the box
independence condition.

The examples provided by Proposition A.2 can be roughly described as semi-
random, in the sense that they are part random and part deterministic. The
following lemma provides us with the random component.

######  Lemma A.4.

Let $d\geqslant 3$ be an integer, and let $\varepsilon>0$. Then there exist a
nonempty finite set $V$ and a symmetric171717That is, for every
$(v_{1},\dots,v_{d-1})\in V^{d-1}$ and every permutation $\pi$ of $[d-1]$ we
have that $(v_{1},\dots,v_{d-1})\in A$ if and only if
$(v_{\pi(1)},\dots,v_{\pi(d-1)})\in A$. subset $A$ of $V^{d-1}$ such that,
denoting by $A^{\complement}$ the complement of $A$, for every pair $F,G$ of
disjoint $($possibly empty$)$ subsets of ${[2d]\choose d-1}$ we have

(A.6) $\displaystyle\Big{|}\int\Big{(}\prod_{s\in
F}\mathbf{1}_{A}(\bm{v}_{s})\Big{)}\cdot\Big{(}\prod_{s\in
G}\mathbf{1}_{A^{\complement}}(\bm{v}_{s})\Big{)}\,d\bm{\mu}(\bm{v})-\Big{(}\frac{1}{2}\Big{)}^{|F|+|G|}\Big{|}\leqslant\varepsilon$

where: _(i)_ $\bm{\mu}$ denotes the product measure on $V^{\mathbb{N}}$
obtained by equipping each factor with the uniform probability measure on $V$,
_(ii)_ for every $\bm{v}=(v_{i})\in V^{\mathbb{N}}$ and every
$s=\\{i_{1}<\dots<i_{d-1}\\}\in{\mathbb{N}\choose d}$ we have
$\bm{v}_{s}=(v_{i_{1}},\dots,v_{i_{d-1}})\in V^{d-1}$, and _(iii)_ in (A.6) we
use the convention that the product of an empty family of functions is equal
to the constant function $1$.

Lemma A.4 follows from a standard random selection and the Azuma–Hoeffding
inequality; see, _e.g._ , [DTV21, Fact 3.3 and Lemma 3.4] for a proof.

We are ready to proceed to the proof of Proposition A.2.

###### Proof of Proposition _A.2_.

Let $V$ and $A$ be the sets obtained by Lemma A.4 applied for

(A.7) $\varepsilon\coloneqq\min\big{\\{}\delta
2^{-d2^{d}},8^{-1}2^{-(d+2)2^{d}}\big{\\}}$

and observe that $V$ can be selected so that its cardinality is an even
positive integer. We also note that in the rest of the proof we follow the
notational conventions in Lemma A.4.

First, for every $i\in[d]$ we define $h^{0}_{i},h^{1}_{i}\colon
V^{d}\to\\{0,1\\}$ by setting for every $\bm{v}\in V^{d}$

(A.8) $\displaystyle
h^{0}_{i}(\bm{v})\coloneqq\mathbf{1}_{A}(\bm{v}_{[d]\setminus\\{i\\}})\ \text{
and }\
h^{1}_{i}(\bm{v})\coloneqq\mathbf{1}_{A^{\complement}}(\bm{v}_{[d]\setminus\\{i\\}}).$

Next, for every $\bm{x}\in\\{0,1\\}^{d}$ define $h_{\bm{x}}\colon
V^{d}\to\\{0,1\\}$ by

(A.9) $\displaystyle h_{\bm{x}}\coloneqq\prod_{i=1}^{d}h_{i}^{\bm{x}(i)}.$

Finally, set

(A.10)
$\mathbb{A}\coloneqq\big{\\{}\bm{x}\in\\{0,1\\}^{d}:\bm{x}(1)+\cdots+\bm{x}(d)\text{
is even}\big{\\}}$

and define $H\colon V^{d}\to\\{0,1\\}$ by

(A.11) $\displaystyle H\coloneqq\sum_{\bm{x}\in\mathbb{A}}h_{\bm{x}}.$

For instance, if $d=3$, then

$\displaystyle H(v_{1},v_{2},v_{3})$
$\displaystyle=\mathbf{1}_{A}(v_{1},v_{2})\mathbf{1}_{A}(v_{2},v_{3})\mathbf{1}_{A}(v_{1},v_{3})+\mathbf{1}_{A^{\complement}}(v_{1},v_{2})\mathbf{1}_{A^{\complement}}(v_{2},v_{3})\mathbf{1}_{A}(v_{1},v_{3})+$
$\displaystyle\ \ \
+\mathbf{1}_{A^{\complement}}(v_{1},v_{2})\mathbf{1}_{A}(v_{2},v_{3})\mathbf{1}_{A^{\complement}}(v_{1},v_{3})+\mathbf{1}_{A}(v_{1},v_{2})\mathbf{1}_{A^{\complement}}(v_{2},v_{3})\mathbf{1}_{A^{\complement}}(v_{1},v_{3}).$

Note that the function $H$ is symmetric181818That is, we have
$H(v_{1},\dots,v_{d})=H(v_{\pi(1)},\dots,v_{\pi(d)})$ for every
$(v_{1},\dots,v_{d})\in V^{d}$ and every permutation $\pi$ of $[d]$.. In the
following series of claims we isolate several properties of $H$ which will be
used in the proofs of properties ($\mathcal{P}$1)–($\mathcal{P}$5).

######  Claim A.5.

For every $k\in[d+1]$ set
$t_{k}\coloneqq\\{k,\dots,k+d-1\\}\in{\mathbb{N}\choose d}$. Then we have

(A.12) $\Big{|}\int
H(\bm{v}_{t_{1}})\,d\bm{\mu}(\bm{v})-\frac{1}{2}\Big{|}\leqslant
2^{d-1}\varepsilon.$

Moreover, for every $k\in\\{2,\dots,d+1\\}$ we have

(A.13) $\Big{|}\int
H(\bm{v}_{t_{1}})H(\bm{v}_{t_{k}})\,d\bm{\mu}(\bm{v})-\frac{1}{4}\Big{|}\leqslant
2^{2d-3}\varepsilon.$

###### Proof of Claim _A.5_.

First observe that (A.12) follows from (A.6), the fact that
$|\mathbb{A}|=2^{d-1}$ and the definition of $H$. Next, fix
$k\in\\{2,\dots,d+1\\}$. Then, for every $\bm{v}\in V^{\mathbb{N}}$ we have

(A.14)
$H(\bm{v}_{t_{1}})H(\bm{v}_{t_{k}})=\sum_{\bm{x},\bm{y}\in\mathbb{A}}\Big{(}\prod_{i=1}^{d}h_{i}^{\bm{x}(i)}(\bm{v}_{t_{1}})\Big{)}\Big{(}\prod_{j=1}^{d}h_{j}^{\bm{y}(j)}(\bm{v}_{t_{k}})\Big{)}.$

Therefore, if $k>2$, then (A.13) also follows from (A.6) and the fact that
$|\mathbb{A}|=2^{d-1}$. So assume that $k=2$. By (A.14), for every $\bm{v}\in
V^{\mathbb{N}}$ we have

(A.15)
$H(\bm{v}_{t_{1}})H(\bm{v}_{t_{2}})=\sum_{\bm{x},\bm{y}\in\mathbb{A}}\Big{(}\prod_{i=2}^{d}h_{i}^{\bm{x}(i)}(\bm{v}_{t_{1}})\Big{)}\Big{(}\prod_{j=1}^{d-1}h_{j}^{\bm{y}(j)}(\bm{v}_{t_{2}})\Big{)}h_{1}^{\bm{x}(1)}(\bm{v}_{t_{1}})h_{d}^{\bm{y}(d)}(\bm{v}_{t_{2}}).$

Notice that for every $\bm{v}\in V^{\mathbb{N}}$ we have
$h^{0}_{\bm{v}_{t_{1}}}=h^{0}_{\bm{v}_{t_{2}}}$ and
$h^{1}_{\bm{v}_{t_{1}}}=h^{1}_{\bm{v}_{t_{2}}}$. Thus, setting
$\mathcal{W}\coloneqq\\{(\bm{x},\bm{y})\in\mathbb{A}\times\mathbb{A}:\bm{x}(1)=\bm{y}(d)\\}$,
we see that
$h_{1}^{\bm{x}(1)}(\bm{v}_{t_{1}})h_{d}^{\bm{y}(d)}(\bm{v}_{t_{2}})=0$ for
every $(\bm{x},\bm{y})\in\mathbb{A}\times\mathbb{A}\setminus\mathcal{W}$.
Combining this information with (A.15), we obtain that

(A.16)
$H(\bm{v}_{t_{1}})H(\bm{v}_{t_{2}})=\sum_{(\bm{x},\bm{y})\in\mathcal{W}}\Big{(}\prod_{i=2}^{d}h_{i}^{\bm{x}(i)}(\bm{v}_{t_{1}})\Big{)}\Big{(}\prod_{j=1}^{d-1}h_{j}^{\bm{y}(j)}(\bm{v}_{t_{2}})\Big{)}h_{1}^{\bm{x}(1)}(\bm{v}_{t_{1}})h_{d}^{\bm{y}(d)}(\bm{v}_{t_{2}})$

for every $\bm{v}\in V^{\mathbb{N}}$. On the other hand, by (A.6), for every
$(\bm{x},\bm{y})\in\mathcal{W}$ we have

(A.17)
$\Big{|}\int\Big{(}\prod_{i=2}^{d}h_{i}^{\bm{x}(i)}(\bm{v}_{t_{1}})\Big{)}\Big{(}\prod_{j=1}^{d-1}h_{j}^{\bm{y}(j)}(\bm{v}_{t_{2}})\Big{)}h_{1}^{\bm{x}(1)}(\bm{v}_{t_{1}})h_{d}^{\bm{y}(d)}(\bm{v}_{t_{2}})\,d\bm{\mu}(\bm{v})-\Big{(}\frac{1}{2}\Big{)}^{2d-1}\Big{|}\leqslant\varepsilon.$

Since $|\mathcal{W}|=2^{2d-3}$, we conclude that (A.13) for $k=2$ follows from
(A.16) and (A.17). The proof of Claim A.5 is completed. ∎

######  Claim A.6.

Set $C\coloneqq\big{\\{}u\cup\\{2d-1\\}:u\in\mathrm{Box}(d-1)\big{\\}}$ where
$\mathrm{Box}(d-1)$ is as in (3.2). $($Notice that
$C\subseteq{\mathbb{N}\choose d}$.$)$ Then we have

(A.18) $\Big{|}\int\prod_{s\in
C}H(\bm{v}_{s})\,d\bm{\mu}(\bm{v})-\Big{(}\frac{1}{2}\Big{)}^{|C|}\Big{|}\leqslant(d+1)2^{d-2+(d-1)2^{d-2}}\varepsilon.$

###### Proof of Claim _A.6_.

We start by setting $j_{i}^{0}\coloneqq 2i-1$ and $j_{i}^{1}\coloneqq 2i$ for
every $i\in[d-1]$. Next, for every
$\bm{\epsilon}=(\epsilon_{i})_{i=1}^{d-1}\in\\{0,1\\}^{d-1}$ set
$s(\bm{\epsilon})\coloneqq\big{\\{}j_{i}^{\epsilon_{i}}:i\in[d-1]\big{\\}}\cup\\{2d-1\\}$,
and notice that
$C=\big{\\{}s(\bm{\epsilon}):\bm{\epsilon}\in\\{0,1\\}^{d-1}\big{\\}}$.
Moreover, by (A.9) and (A.11), we have

(A.19) $\displaystyle\int\prod_{s\in C}H(\bm{v}_{s})\,d\bm{\mu}(\bm{v})$
$\displaystyle=\int\prod_{\bm{\epsilon}\in\\{0,1\\}^{d-1}}H(\bm{v}_{s(\bm{\epsilon})})\,d\bm{\mu}(\bm{v})=$
$\displaystyle=\sum_{(\bm{x}_{\bm{\epsilon}})_{\bm{\epsilon}\in\\{0,1\\}^{d-1}}\in\mathbb{A}^{\\{0,1\\}^{d-1}}}\int\prod_{\bm{\epsilon}\in\\{0,1\\}^{d-1}}h_{\bm{x}_{\bm{\epsilon}}}(\bm{v}_{s(\bm{\epsilon})})\,d\bm{\mu}(\bm{v}).$

We define a subset $\mathcal{R}$ of $\mathbb{A}^{\\{0,1\\}^{d-1}}$ by the rule

(A.20)
$\displaystyle(\bm{x}_{\bm{\epsilon}})_{\bm{\epsilon}\in\\{0,1\\}^{d-1}}\in\mathcal{R}\Leftrightarrow$
$\displaystyle\text{ for every }j\in[d-1],\text{ every
}\bm{\epsilon}=(\epsilon_{i})_{i=1}^{d-1}\in\\{0,1\\}^{d-1}$
$\displaystyle\text{ and every
}\bm{\epsilon}^{\prime}=(\epsilon^{\prime}_{i})_{i=1}^{d-1}\in\\{0,1\\}^{d-1}$
$\displaystyle\text{ with }\epsilon_{i}=\epsilon^{\prime}_{i}\text{ for all
}i\in[d-1]\setminus\\{j\\}$ $\displaystyle\text{ we have
}\bm{x}_{\bm{\epsilon}}(j)=\bm{x}_{\bm{\epsilon}^{\prime}}(j).$

Figure 6. The structure of the set $\mathcal{R}$ for $d=3$. Connected dots
imply equality of the corresponding coordinates.

Observe that for every $j\in[d-1]$ and every
$\bm{\epsilon}=(\epsilon_{i})_{i=1}^{d-1},\bm{\epsilon}^{\prime}=(\epsilon^{\prime}_{i})_{i=1}^{d-1}\in\\{0,1\\}^{d-1}$
with $\epsilon_{i}=\epsilon^{\prime}_{i}$ for all $i\in[d-1]\setminus\\{j\\}$
we have
$h_{j}^{0}(\bm{v}_{s(\bm{\epsilon})})=h_{j}^{0}(\bm{v}_{s(\bm{\epsilon}^{\prime})})$
and
$h_{j}^{1}(\bm{v}_{s(\bm{\epsilon})})=h_{j}^{1}(\bm{v}_{s(\bm{\epsilon}^{\prime})})$
for every $\bm{v}\in V^{\mathbb{N}}$ which, in turn, implies that
$h_{j}^{0}(\bm{v}_{s(\bm{\epsilon})})h_{j}^{1}(\bm{v}_{s(\bm{\epsilon}^{\prime})})=0$.
Consequently,
$\prod_{\bm{\epsilon}\in\\{0,1\\}^{d-1}}h_{\bm{x}_{\bm{\epsilon}}}(\bm{v}_{s(\bm{\epsilon})})=0$
for every
$(\bm{x}_{\bm{\epsilon}})_{\bm{\epsilon}\in\\{0,1\\}^{d-1}}\in\mathbb{A}^{\\{0,1\\}^{d-1}}\setminus\mathcal{R}$
and every $\bm{v}\in V^{\mathbb{N}}$. Therefore, by (A.19), we obtain that

(A.21) $\int\prod_{s\in
C}H(\bm{v}_{s})\,d\bm{\mu}(\bm{v})=\sum_{(\bm{x}_{\bm{\epsilon}})_{\bm{\epsilon}\in\\{0,1\\}^{d-1}}\in\mathcal{R}}\int\prod_{\bm{\epsilon}\in\\{0,1\\}^{d-1}}h_{\bm{x}_{\bm{\epsilon}}}(\bm{v}_{s(\bm{\epsilon})})\,d\bm{\mu}(\bm{v}).$

On the other hand, by (A.6), for every
$(\bm{x}_{\bm{\epsilon}})_{\bm{\epsilon}\in\\{0,1\\}^{d-1}}\in\mathcal{R}$ we
have

(A.22)
$\displaystyle\Big{|}\int\prod_{\bm{\epsilon}\in\\{0,1\\}^{d-1}}h_{\bm{x}_{\bm{\epsilon}}}(\bm{v}_{s(\bm{\epsilon})})\,d\bm{\mu}(\bm{v})-\Big{(}\frac{1}{2}\Big{)}^{(d+1)2^{d-2}}\Big{|}$
$\displaystyle=\,\Big{|}\int$
$\displaystyle\prod_{i=1}^{d}\prod_{\bm{\epsilon}\in\\{0,1\\}^{d-1}}h_{i}^{\bm{x}_{\bm{\epsilon}}(i)}(\bm{v}_{s(\bm{\epsilon})})\,d\bm{\mu}(\bm{v})-\Big{(}\frac{1}{2}\Big{)}^{(d+1)2^{d-2}}\Big{|}$
$\displaystyle=\,\Big{|}\int$
$\displaystyle\Big{(}\prod_{i=1}^{d-1}\prod_{\bm{\epsilon}\in\\{0,1\\}^{d-1}}h_{i}^{\bm{x}_{\bm{\epsilon}}(i)}(\bm{v}_{s(\bm{\epsilon})})\Big{)}\Big{(}\prod_{\bm{\epsilon}\in\\{0,1\\}^{d-1}}h_{d}^{\bm{x}_{\bm{\epsilon}}(d)}(\bm{v}_{s(\bm{\epsilon})})\Big{)}\,d\bm{\mu}(\bm{v})-\Big{(}\frac{1}{2}\Big{)}^{(d+1)2^{d-2}}\Big{|}$
$\displaystyle\leqslant(d+$ $\displaystyle 1)2^{d-2}\varepsilon.$

The estimate (A.18) follows from (A.21), (A.22), and the fact that
$|\mathcal{R}|=2^{(d-1)2^{d-2}}$ and $|C|=2^{d-1}$. The proof of Claim A.6 is
completed. ∎

######  Claim A.7.

Let $\mathrm{Box}(d)$ be as in (3.2). Then we have

(A.23)
$\Big{|}\int\prod_{s\in\mathrm{Box}(d)}H(\bm{v}_{s})d\bm{\mu}(\bm{v})-2\Big{(}\frac{1}{2}\Big{)}^{|\mathrm{Box}(d)|}\Big{|}\leqslant
d2^{d+(d-2)2^{d-1}}\varepsilon.$

###### Proof of Claim _A.7_.

As in the proof of Claim A.6, for every $i\in[d]$ set $j_{i}^{0}\coloneqq
2i-1$ and $j_{i}^{1}\coloneqq 2i$. Moreover, for every
$\bm{\epsilon}=(\epsilon_{i})_{i=1}^{d}\in\\{0,1\\}^{d}$ set
$s(\bm{\epsilon})\coloneqq\big{\\{}j_{i}^{\epsilon_{i}}:i\in[d]\big{\\}}$, and
observe that
$\mathrm{Box}(d)=\big{\\{}s(\bm{\epsilon}):\bm{\epsilon}\in\\{0,1\\}^{d}\big{\\}}$.
We define a subset $\mathcal{Q}$ of $\mathbb{A}^{\\{0,1\\}^{d}}$ by setting

(A.24)
$\displaystyle(\bm{x}_{\bm{\epsilon}})_{\bm{\epsilon}\in\\{0,1\\}^{d}}\in\mathcal{Q}\Leftrightarrow$
$\displaystyle\text{ for every }j\in[d],\text{ every
}\bm{\epsilon}=(\epsilon_{i})_{i=1}^{d}\in\\{0,1\\}^{d}$ $\displaystyle\text{
and every
}\bm{\epsilon}^{\prime}=(\epsilon^{\prime}_{i})_{i=1}^{d}\in\\{0,1\\}^{d}$
$\displaystyle\text{ with }\epsilon_{i}=\epsilon^{\prime}_{i}\text{ for all
}i\in[d]\setminus\\{j\\}$ $\displaystyle\text{ we have
}\bm{x}_{\bm{\epsilon}}(j)=\bm{x}_{\bm{\epsilon}^{\prime}}(j).$

Figure 7. The structure of the set $\mathcal{Q}$ for $d=3$. As in Figure $6$,
connected dots imply equality of the corresponding coordinates.

By (A.9), (A.11), the definition of $\mathcal{Q}$ and arguing as in the proof
of Claim A.6,

(A.25)
$\displaystyle\int\prod_{s\in\mathrm{Box}(d)}H(\bm{v}_{s})\,d\bm{\mu}(\bm{v})$
$\displaystyle=\int\prod_{\bm{\epsilon}\in\\{0,1\\}^{d}}H(\bm{v}_{s(\bm{\epsilon})})\,d\bm{\mu}(\bm{v})$
$\displaystyle=\sum_{(\bm{x}_{\bm{\epsilon}})_{\bm{\epsilon}\in\\{0,1\\}^{d}}\in\mathbb{A}^{\\{0,1\\}^{d}}}\int\prod_{\bm{\epsilon}\in\\{0,1\\}^{d}}h_{\bm{x}_{\bm{\epsilon}}}(\bm{v}_{s(\bm{\epsilon})})\,d\bm{\mu}(\bm{v})$
$\displaystyle=\sum_{(\bm{x}_{\bm{\epsilon}})_{\bm{\epsilon}\in\\{0,1\\}^{d}}\in\mathcal{Q}}\int\prod_{\bm{\epsilon}\in\\{0,1\\}^{d}}h_{\bm{x}_{\bm{\epsilon}}}(\bm{v}_{s(\bm{\epsilon})})\,d\bm{\mu}(\bm{v}).$

By (A.6), for every
$(\bm{x}_{\bm{\epsilon}})_{\bm{\epsilon}\in\\{0,1\\}^{d-1}}\in\mathcal{Q}$ we
have

(A.26)
$\Big{|}\int\prod_{\bm{\epsilon}\in\\{0,1\\}^{d}}h_{\bm{x}_{\bm{\epsilon}}}(\bm{v}_{s(\bm{\epsilon})})\,d\bm{\mu}(\bm{v})-\Big{(}\frac{1}{2}\Big{)}^{d2^{d-1}}\Big{|}\leqslant
d2^{d-1}\varepsilon.$

Finally, note that $|Q|=2^{(d-2)2^{d-1}+1}$. Using this information, (A.23)
follows from (A.25), (A.26) and the fact that $|\mathrm{Box}(d)|=2^{d}$. The
proof of Claim A.7 is completed. ∎

######  Claim A.8.

Let $B$ be a $d$-dimensional box of $\mathbb{N}$ such that $\min(s)\geqslant
2d+1$ for every $s\in B$. Then we have

(A.27) $\Big{|}\int\prod_{s\in\mathrm{Box}(d)\cup
B}H(\bm{v}_{s})\,d\bm{\mu}(\bm{v})-4\Big{(}\frac{1}{2}\Big{)}^{2|\mathrm{Box}(d)|}\Big{|}\leqslant
d2^{d+1+(d-2)2^{d-1}}\varepsilon.$

###### Proof of Claim _A.8_.

It follows immediately by Claim A.7. ∎

After this preliminary discussion, we now enter into the main part of the
proof. Let $\bm{X}=\langle X_{s}:s\in{\mathbb{N}\choose d}\rangle$ be a
boolean, exchangeable, $d$-dimensional random array on $\mathbb{N}$ whose
distribution satisfies

(A.28)
$\mathbb{E}\Big{[}\prod_{s\in\mathcal{F}}X_{s}\Big{]}=\frac{1}{2}\Big{(}\frac{1}{2}\Big{)}^{|\mathcal{F}|}+\frac{1}{2}\int\prod_{s\in\mathcal{F}}H(\bm{v}_{s})\,d\bm{\mu}(\bm{v})$

for every nonempty finite subset $\mathcal{F}$ of ${\mathbb{N}\choose d}$.
(The existence of such a random array follows arguing precisely as in the
proof of Proposition A.1.)

First, we will show that $\bm{X}$ satisfies properties ($\mathcal{P}$1) up to
($\mathcal{P}$4). For property ($\mathcal{P}$1), let $s\in{\mathbb{N}\choose
d}$ be arbitrary and notice that, by the exchangeability of $\bm{X}$ and
(A.28),

(A.29) $\mathbb{E}[X_{s}]=\frac{1}{4}+\frac{1}{2}\int
H(\bm{v}_{t_{1}})\,d\bm{\mu}(\bm{v})$

where, as in Claim A.5, we have $t_{1}=\\{1,\dots,d\\}$. By (A.12) and the
choice of $\varepsilon$ in (A.7), we obtain that
$\big{|}\mathbb{E}[X_{s}]-\frac{1}{2}\big{|}\leqslant
2^{d-2}\varepsilon\leqslant\delta$. For property ($\mathcal{P}$2), let
$s,t\in{\mathbb{N}\choose d}$ be distinct, and set $k\coloneqq d-|s\cap t|+1$.
Since $\bm{X}$ is exchangeable, by (A.28), we have

(A.30) $\displaystyle\mathbb{E}[X_{s}X_{t}]=\frac{1}{8}+\frac{1}{2}\int
H(\bm{v}_{t_{1}})H(\bm{v}_{t_{k}})\,d\bm{\mu}(\bm{v})$

where $t_{1}$ and $t_{k}$ are as in Claim A.5. By (A.13), (A.30) and invoking
again (A.7), we see that
$\big{|}\mathbb{E}[X_{s}X_{t}]-\frac{1}{4}\big{|}\leqslant
2^{2d-4}\varepsilon\leqslant\delta$. For property ($\mathcal{P}$3), let $F$ be
a $(d-1)$-face of $\mathbb{N}$. By the exchangeability of $\bm{X}$, (A.28) and
the choice of the set $C$ in Claim A.6,

(A.31) $\displaystyle\mathbb{E}\Big{[}\prod_{s\in
F}X_{s}\Big{]}=\frac{1}{2}\Big{(}\frac{1}{2}\Big{)}^{|F|}+\frac{1}{2}\int\prod_{s\in
C}H(\bm{v}_{s})\,d\bm{\mu}(\bm{v})$

which implies, by (A.18), that

(A.32) $\Big{|}\mathbb{E}\Big{[}\prod_{s\in
F}X_{s}\Big{]}-\Big{(}\frac{1}{2}\big{)}^{|F|}\Big{|}\leqslant(d+1)2^{d-3+(d-1)2^{d-2}}\varepsilon\stackrel{{\scriptstyle\eqref{ea.7}}}{{\leqslant}}\delta.$

Lastly, for property ($\mathcal{P}$4), let $B$ be a $d$-dimensional box of
$\mathbb{N}$. Using once again the exchangeability of $\bm{X}$ and (A.28), we
see that

(A.33) $\displaystyle\mathbb{E}\Big{[}\prod_{s\in
B}X_{s}\Big{]}=\frac{1}{2}\Big{(}\frac{1}{2}\Big{)}^{|B|}+\frac{1}{2}\int\prod_{s\in\mathrm{Box}(d)}H(\bm{v}_{s})\,d\bm{\mu}(\bm{v})$

and so, by (A.23),

(A.34) $\Big{|}\mathbb{E}\Big{[}\prod_{s\in
B}X_{s}\Big{]}-\frac{3}{2}\Big{(}\frac{1}{2}\Big{)}^{|B|}\Big{|}\leqslant
d2^{d-1+(d-2)2^{d-1}}\varepsilon\stackrel{{\scriptstyle\eqref{ea.7}}}{{\leqslant}}\delta.$

Thus, it remains to verify property ($\mathcal{P}$5). As expected, we will
argue as in Proposition 2.8. Specifically, fix an integer $n\geqslant 4d$, and
define $f\colon\mathbb{R}^{[n]\choose d}\to\mathbb{R}$ by setting for every
$\bm{x}=(x_{t})_{t\in{[n]\choose d}}\in\mathbb{R}^{[n]\choose d}$

(A.35)
$f(\bm{x})\coloneqq\prod_{s\in\mathrm{Box}(d)}\\!\\!x_{s}-\mathbb{E}\Big{[}\prod_{s\in\mathrm{Box}(d)}\\!\\!X_{s}\Big{]}.$

Clearly, $f$ is a translated multilinear polynomial of degree $2^{d}$ and
satisfies $\mathbb{E}[f(\bm{X}_{n})]=0$ and
$\|f(\bm{X}_{n})\|_{L_{\infty}}\leqslant 1$. On the other hand, if $B$ is a
$d$-dimensional box on $\mathbb{N}$ such that $\min(s)\geqslant 2d+1$ for
every $s\in B$, then

(A.36) $\displaystyle\mathbb{E}\Big{[}\prod_{s\in\mathrm{Box}(d)\cup
B}X_{s}\Big{]}\stackrel{{\scriptstyle\eqref{ea.28}}}{{=}}\frac{1}{2}\Big{(}\frac{1}{2}\Big{)}^{2^{d+1}}+\frac{1}{2}\int\prod_{s\in\mathrm{Box}(d)\cup
B}H(\bm{v}_{s})\,d\bm{\mu}(\bm{v})$

and so, by (A.27),

(A.37) $\Big{|}\mathbb{E}\Big{[}\prod_{s\in\mathrm{Box}(d)\cup
B}X_{s}\Big{]}-\frac{5}{2}\Big{(}\frac{1}{2}\Big{)}^{2^{d+1}}\Big{|}\leqslant
d2^{d+(d-2)2^{d-1}}\varepsilon.$

Using this estimate, property ($\mathcal{P}$4) and arguing as in the proof of
Proposition A.1, it is easy to verify that the function $f$ satisfies property
($\mathcal{P}$5). The proof of Proposition A.2 is completed. ∎

### References

  * [AdWo15] R. Adamczak and P. Wolff, Concentration inequalities for non-Lipschitz functions with bounded derivatives of higher order, Probab. Theory Related Fields 162 (2015), 531–586.
  * [Ald81] D. J. Aldous, Representations for partially exchangeable arrays of random variables, J. Multivariate Anal. 11 (1981), 581–597.
  * [Au08] T. Austin, On exchangeable random variables and the statistics of large graphs and hypergraphs, Probability Surveys 5 (2008), 80–145.
  * [Au11] T. Austin, Deducing the density Hales–Jewett theorem from an infinitary removal lemma, J. Theor. Probab. 24 (2011), 615–633.
  * [Au13] T. Austin, Exchangeable random arrays, preprint (2013), available at https://www.math.ucla.edu/~tim/ExchnotesforIISc.pdf.
  * [Ber96] V. Bergelson, Ergodic Ramsey theory—an update, in “Ergodic Theory of $\mathbb{Z}^{d}$-Actions”, London Mathematical Society Lecture Note Series, Vol. 228, Cambridge University Press, 1996, 1–61.
  * [Bob04] S. Bobkov, Concentration of normalized sums and a central limit theorem for noncorrelated random variables, Ann. Probab. 32 (2004), 2884–2908.
  * [BLM13] S. Boucheron, G. Lugosi and P. Massart, Concentration Inequalities. A Nonasymptotic Theory of Independence, Oxford University Press, 2013.
  * [Ch06] S. Chatterjee, A generalization of the Lindeberg principle, Ann. Probab. 34 (2006), 2061–2076.
  * [CGW88] F. R. K. Chung, R. L. Graham and R. M. Wilson, Quasi-random graphs, Proc. Natl. Acad. Sci. USA 85 (1988), 969–970.
  * [CGW89] F. R. K. Chung, R. L. Graham and R. M. Wilson, Quasi-random graphs, Combinatorica 9 (1989), 345–362.
  * [DF80] P. Diaconis and D. Freedman, Finite exchangeable sequences, Ann. Probab. 8 (19180), 745–764.
  * [DK16] P. Dodos and V. Kanellopoulos, Ramsey Theory for Product Spaces, Mathematical Surveys and Monographs, Vol. 212, American Mathematical Society, 2016.
  * [DKK16] P. Dodos, V. Kanellopoulos and Th. Karageorgos, Szemerédi’s regularity lemma via martingales, Electron. J. Combin. 23 (2016), Research Paper P3.11, 1–24.
  * [DKT16] P. Dodos, V. Kanellopoulos and K. Tyros, A concentration inequality for product spaces, J. Funct. Anal. 270 (2016), 609–620.
  * [DT21] P. Dodos and K. Tyros, A structure theorem for stochastic processes indexed by the discrete hypercube, Forum Math. Sigma 9 (2021), Paper No. e8, 1–30.
  * [DTV21] P. Dodos, K. Tyros and P. Valettas, Decompositions of finite high-dimensional random arrays, preprint (2021), available at https://arxiv.org/abs/2102.11102.
  * [ER52] P. Erdős and R. Rado, Combinatorial theorems on classifications of subsets of a given set, Proc. London Math. Soc. 2 (1952), 417–439.
  * [FT85] D. H. Fremlin and M. Talagrand, Subgraphs of random graphs, Trans. Amer. Math. Soc. 291 (1985), 551–582.
  * [FK91] H. Furstenberg and Y. Katznelson, A density version of the Hales–Jewett theorem, J. Anal. Math. 57 (1991), 64–117.
  * [GSS19] F. Götze, H. Sambale and A. Sinulis, Concentration inequalities for polynomials in $\alpha$-sub-exponential random variables, preprint (2019), available at https://arxiv.org/abs/1903.05964.
  * [Go07] W. T. Gowers, Hypergraph regularity and the multidimensional Szemerédi theorem, Ann. Math. 166 (2007), 897–946.
  * [Go09] W. T. Gowers, The first unknown case of polynomial DHJ, blog post (2009), available at https://gowers.wordpress.com/2009/11/14/the-first-unknown-case-of-polynomial-dhj/.
  * [GT10] B. Green and T. Tao, Linear equations in primes, Ann. Math. 171 (2010), 1753–1850.
  * [GG71] V. I. Gurarii and N. I. Gurarii, On bases in uniformly convex and uniformly smooth Banach spaces, Izv. Akad. Nauk SSSR Ser. Mat. 35 (1971), 210–215.
  * [Hoo79] D. N. Hoover, Relations on probability spaces and arrays of random variables, preprint (1979), available at https://www.stat.berkeley.edu/~aldous/Research/hoover.pdf.
  * [Ja72] R. C. James, Super-reflexive spaces with bases, Pac. J. Math. 41 (1972), 409–417.
  * [Kal92] O. Kallenberg, Symmetries on random arrays and set-indexed processes, J. Theor. Probab. 5 (1992), 727–765.
  * [Kal05] O. Kallenberg, Probabilistic Symmetries and Invariance Principles, Probability and its Applications (New York), Springer, 2005.
  * [La06] R. Latala, Estimates of moments and tails of Gaussian chaoses, Ann. Probab. 34 (2006), 2315–2331.
  * [Le01] M. Ledoux, The Concentration of Measure Phenomenon, Mathematical Surveys and Monographs, Vol. 89, American Mathematical Society, 2001.
  * [Lov12] L. Lovász, Large networks and graph limits, Colloquium Publications, Vol. 60, American Mathematical Society, 2012.
  * [MS75] W. G. Moginley and R. Sibson, Dissociated random variables, Math. Proc. Cambridge Philos. Soc. 77 (1975), 185–187.
  * [Pi11] G. Pisier, Martingales in Banach Spaces $($in connection with Type and Cotype$)$, preprint (2011), available at http://www.math.jussieu.fr/~pisier/ihp-pisier.pdf.
  * [Pi16] G. Pisier, Martingales in Banach Spaces, Cambridge Studies in Advanced Mathematics, Vol. 155, Cambridge University Press, 2016.
  * [Ra30] F. P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. 30 (1930), 264–286.
  * [RX16] E. Ricard and Q. Xu, A noncommutative martingale convexity inequality, Ann. Probab. 44 (2016), 867–882.
  * [Rő15] V. Rődl, Quasi-randomness and the regularity method in hypergraphs, in “Proceedings of the International Congress of Mathematicians” Vol. I, 571–599, 2015.
  * [Tao06] T. Tao, Szemerédi’s regularity lemma revisited, Contrib. Discrete Math. 1 (2006), 8–27.
  * [Tao08] T. Tao, Structure and Randomness: Pages from Year One of a Mathematical Blog, American Mathematical Society, 2007.
  * [Tho87] A. Thomason, Pseudo-random graphs, Ann. Discrete Math. 33 (1987), 307–331.
  * [V19] R. Vershynin, Concentration inequalities for random tensors, Bernoulli 26 (2020), 3139–3162.