# Letter of Intent: Open Charm at JLab with the sPHENIX MAPS tracker

Miguel Arratia  Corresponding author<EMAIL_ADDRESS>University of
California, Riverside  Sebouh J. Paul  University of California, Riverside
Yuri Gotra  Thomas Jefferson National Accelerator Facility  Hayk Hakobyan
Universidad Tecnica Federico Santa Maria, Valparaiso, Chile  Bryan McKinnon
University of Glasgow, Glasgow, United Kingdom

###### Abstract

We propose a physics program at JLab with CLAS12 focusing on open-charm
measurements, aiming to complement and expand current studies of $J/\psi$ at
(sub) threshold. This program will aid us in elucidating the $J/\psi$
production mechanisms, which is crucial for interpreting data in terms of
gluon form factors and offer potential insights into the intrinsic charm
hypothesis and cold-nuclear matter effects. We discuss the technical
feasibility of integrating the sPHENIX monolithic-active-pixel sensor (MAPS)
tracker, known as MVTX, with the CLAS12 detector. The sPHENIX MTVX would
support an open-charm program by providing excellent secondary-vertex
performance for tagging $D$ mesons. We study the kinematics of $\gamma
p\to\bar{D}^{0}\Lambda_{c}$ through phase-space simulations and estimate rates
for the tagged quasi-photoproduction regime available with the CLAS12 forward
tagger. While open-charm cross-sections at threshold remain uncertain, various
predictions suggest that these measurements could be feasible when combined
with conservative estimates of detector acceptance and luminosity. These
preliminary estimates motivate detailed Geant detector simulations of signals
and backgrounds, along with thorough technical assessments of operating
conditions, to further explore the feasibility of these measurements in future
dedicated CLAS12 experiments at JLab.

††preprint: APS/123-QED

###### Contents

  1. I Motivation for a Measurement of Open-Charm production at Threshold
  2. II Experimental Setup
    1. II.1 The sPHENIX MAPS Vertex Tracker
    2. II.2 Integration of the MVTX in CLAS12
    3. II.3 Trigger rate, radiation tolerance, material budget
    4. II.4 Triggering with the Forward Tracker
  3. III Observables and Analysis Methods
  4. IV Estimated Reach
    1. IV.1 Total expected cross section
    2. IV.2 Luminosity
    3. IV.3 Monte-Carlo Simulations
    4. IV.4 Estimation of efficiency and acceptance
    5. IV.5 Geometric acceptance of the MVTX
    6. IV.6 MVTX efficiency
    7. IV.7 Event retention after displaced-vertex cut
    8. IV.8 Expected sample size and reach
  5. V Summary and Conclusions

##  I Motivation for a Measurement of Open-Charm production at Threshold

The study of $J/\psi$ photoproduction at threshold has attracted considerable
attention, with the objective of accessing the gluonic structure of the
nucleon, and, ultimately, contributing to our understanding of the origin of
the nucleon mass, see e.g Refs. [1, 2, 3, 4, 5, 6, 7, 8] . This has motivated
various experiments at JLab [9, 10], including GlueX at Hall-D [11, 12], the
$J/\psi$–007 experiment at Hall-C [13], CLAS12 at Hall-B [14, 15], and SoLID
at Hall-A [16].

The analysis of $\gamma p\to J/\psi p$ cross-section measurements typically
relies on the assumption that the reaction mechanism can be described by the
“vector-dominance model” (VDM) as illustrated in the left panel of Figure 1.
Within this framework, the reaction is factorized into a hard $\gamma\to
c\bar{c}$ vertex and a soft proton matrix element. Crucially, this
factorization enables the extraction of the forward elastic-scattering
amplitude of $J/\psi$ off a proton, see e.g Ref. [17, 18, 19, 20].

Figure 1: Left: $J/\psi$ production mechanism as per the vector-dominance
model. Middle: Open-charm production mechanism. Right: $J/\psi$ production
mechanism through open-charm coupled channel suggested by Du et al. [21].
Source: Ref. [21].

Such assumptions have, however, been questioned, for example by Du et al. [21]
who suggested that a the reaction mechanism leading to the $J/\psi$$p$ final
state could at least in part proceed through an open-charm coupled channel,
illustrated in the right panel of Figure 1. In this model, open-charm
production is followed by re-scattering of $\bar{D}$ and $\Lambda_{c}$ to
produce the the $J/\psi$$p$ final state. Note that the energy threshold for
$J/\psi$ photoproduction ($\approx$8.2 GeV) is close to the threshold of the
$\gamma p\to\bar{D}^{0}\Lambda_{c}$ and $\gamma p\to\bar{D}^{*}\Lambda_{c}$
reactions ($\approx$8.7 GeV and $\approx$9.4 GeV, respectively). This
mechanism is not factorized like VDM and is not amenable to the interpretation
of the $\gamma p\to J/\psi p$ data in relation to the gluonic structure of the
nucleon.

The latest measurement of $J/\psi$ at threshold by GlueX [12], shown in the
left panel of Figure 2, revealed intriguing trends in the dataset near
threshold, although with weak statistical significance (2.6$\sigma$). These
features, not initially anticipated within the vector-dominance model, align
with the open-charm mechanism proposed by Du et al.[21]. Notably, the cusp
features appear at the threshold values for both $\gamma
p\to\bar{D}^{0}\Lambda_{c}$ and $\gamma p\to\bar{D}^{*}\Lambda_{c}$.

Figure 2: Left: GlueX measured $J/\psi$ photoproduction near the threshold,
with vertical lines indicating the threshold energy for production of $\gamma
p\to\bar{D}^{0}\Lambda_{c}$ and $\gamma p\to\bar{D}^{*}\Lambda_{c}$. The
curves represent predictions by Du et al. [21]. Source: Ref. [12]. Right: Du
et al. predictions for open-charm production near the threshold, for
$\Lambda_{c}^{+}\bar{D}^{0}$ (blue) and $\Lambda_{c}^{+}\bar{D}^{*0}$
(orange), indicating two scenarios depending on the model parameter $\eta$.
Note how the open-charm cross-section is predicted to be one or two orders of
magnitude higher than the $J/\psi$ cross-section. Source: Ref. [21].

Another intriguing feature not expected in the VDM model was uncovered by the
Hall-C experiment [13], which measured differential double-differential cross-
sections as a function of the momentum transfer, $t$, and photon energy,
$E_{\gamma}$. For the most part, the cross-section is well described by a
falling exponential function in $t$, but some data present an upward trend at
high $t$, which might be expected from $u$-channel exchange.

A partial-wave analysis carried out by the JPAC collaboration [22] suggests
that both features—namely, the cusps in GlueX data and the upward trend in $t$
in Hall-C data—are compatible with the open-charm coupled channel model,
although with large statistical uncertainties. Thus far, the Du et al. model
cannot be ruled out with existing experimental data, or as they put it: “Our
analysis indicates that the present statistics do not exclude severe
violations of factorization and of the Vector Meson Dominance which are
usually assumed in the literature”.

One way to indirectly constrain the open-charm channel scenario would be
through future, higher-statistics $J/\psi$ measurements at GlueX, Hall-C, and
SoLID. A direct alternative arises from the observation that the strength of
the cusp structures and overall cross-sections in GlueX $J/\psi$ data is
related to the open-charm cross-sections., $\gamma
p\to\bar{D}^{0}\Lambda_{c}$, which Du et al. predict to range between one and
two orders of magnitude higher than that of $\gamma p\to$$J/\psi$$p$,
depending on model parameters, as depicted in the right panel of Figure 2.
Therefore, one way to constrain the extent to which the open-charm exchange
mechanism contributes to the total $J/\psi$ cross-section is by measuring the
open-charm cross-section itself, i.e $\gamma p\to\bar{D}^{0}\Lambda_{c}$ and
$\gamma p\to\bar{D}^{*}\Lambda_{c}$. No previous measurement for open-charm
photoproduction exists for photon energies below 20 GeV, making experiments at
JLab 12 GeV rich in discovery potential.

The importance of directly measuring open-charm photoproduction near threshold
has been emphasized in recent work, as evidenced by the following sample of
quotes:

> “Since the strength of the cusps is connected to the rate for $\gamma
> p\to\bar{D}^{0}\Lambda_{c}$, we also provide an estimate for the expected
> rate into the open-charm channels….measurements of the $\bar{D}\Lambda_{c}$
> production will provide crucial information”. Du et al. [21].

> “It is thus crucially important to constrain model parameters with further
> measurements in order to disentangle the possible physics scenarios and
> their implications…the measurement of open-charm photoproduction is needed
> to assess the role of coupled channels. A simultaneous analysis of the
> $\gamma p\to$$J/\psi$ and $\gamma p\to\bar{D}^{0}\Lambda_{c}$ cross sections
> would provide a stringent constraint on the coupled channel dynamics. Based
> on the best fit parameters extracted here, we expect a large open-charm
> cross-section $\gtrsim$ 10 nb. Furthermore, studies of photoproduction off
> nuclear targets may give further constrain on the total $J/\psi$-nucleon
> cross-section.” Winney et al. (JPAC Collaboration) [22].

The cross-section for open-charm photoproduction near threshold is currently
unknown, but measurements have been conducted at higher energies. The lowest-
energy studies were performed at SLAC, where an experiment using a 20 GeV real
photon reported a total open-charm cross-section of $56^{-23}_{+24}$ nb [23,
24]. Another SLAC study used a 10.5 GeV photon beam and reported an upper
limit of 94 nb at a 90% confidence level [25]. The dominant channel for the
energy range of interest is $\gamma p\to\bar{D}^{0}\Lambda_{c}$, which is
expected to dominate the total charm cross-section. The HERMES experiment also
conducted searches for open-charm production in low-energy photoproduction,
with unpublished measurements [26] of $D^{*\pm}$ production suggesting a total
open-charm cross-section of:

$\left[87.9^{+40.7}_{-32.1}\mathrm{(stat)}\pm 9.2\mathrm{(sys)}\pm
17.6\mathrm{(frag.~{}model)}\right]\mathrm{nb}~{}\mathrm{at}~{}E_{\gamma}=15~{}\mathrm{GeV}$
(1)

Tomasi-Gustafsson [27] predicts the $\gamma p\to\bar{D}^{0}\Lambda_{c}$ cross-
section to be approximately 40 nb at a photon energy of $10$ GeV. As shown in
Fig. 2, Du et al. predict an open-charm cross-section within the range of
50–100 nb for the 9–10 GeV range under one assumption, and 20–30 nb under an
alternative set of model parameters. For comparison, the GlueX data reveals a
$\gamma p\rightarrow J/\psi$ cross-section in the 9–10 GeV range that is
approximately 0.3–1 nb (as shown in Figure 2).

##  II Experimental Setup

We envision taking advantage of the lifetime of the charmed hadrons by using a
cut in the displaced vertex position relative to a thin target or prompt
particles. The charmed mesons and baryons will travel
$\mathcal{O}(100\,\mu{\rm m})$ before decaying. To measure this requires two
key ingredients in our proposed experimental setup. The first is a thin target
with a thickness not much greater than 100$\mu{\rm m}$. The second requirement
is we need to have a vertex resolution that is much smaller than the decay
lengths. In the current CLAS12 setup, the vertex resolution is insufficient
for this purpose. Instead, we will propose to borrow an existing detector, the
MAPS Vertex tracker (MVTX) from the sPHENIX experiment, and insert it inside
the CLAS12 Central Vertex Tracker. This displaced-vertex strategy is much more
promising than relying solely on the CLAS12 PID systems, which would serve as
the baseline for these searches but have limited momentum range and coverage.
This possible detector setup is described in detail Sec. II.1 below, and we
describe its integration in CLAS12 in Sec. II.2.

###  II.1 The sPHENIX MAPS Vertex Tracker

sPHENIX is an ongoing experiment at RHIC [28], primarily dedicated to the
study of quark-gluon plasma. At the heart of sPHENIX lies the Monolithic-
Active-Pixel-Sensor (MAPS) vertex detector known as MVTX [29]. This detector
is designed to track the vertices of particles generated from proton-proton
and nucleus-nucleus collisions. More specifically, MVTX plays a crucial role
in a physics program centered on the measurement of displaced vertices as
signatures of heavy-quarks (charm and bottom) mesons and baryons. For
reference, the single-track performance of MVTX within the 1.4 T solenoid
field of sPHENIX is 40 $\mu$m for pointing resolution of distance-of-closest
approach (DCA) for tracks with 0.5–1 GeV transverse momentum, and an
efficiency of 80$\%$.

The nominal layout of the MVTX in sPHENIX is defined with a barrel geometry,
featuring an active length of 27 cm, with layer radial positions ranging from
22.4 to 42.1 mm. Its services are routed through a carbon-fiber cone structure
from just one side of the detector. Figure 3 shows a picture of part of MVTX
and services prior to installation in sPHENIX.

Figure 3: Half of the sPHENIX MVTX detector and services prior to installation
in sPHENIX. Figure credit: BNL/sPHENIX

###  II.2 Integration of the MVTX in CLAS12

We illustrate in Fig. 4 a potential layout for the MVTX within CLAS12, which
would use the nominal geometry of the CLAS central trackers (CVT and FMT) and
5 T solenoid, as well as the nominal geometry of MVTX as used in sPHENIX. This
layout would be possible by removing the vacuum chamber typically housing a
cryotarget for liquid hydrogen or deuterium, thereby creating room for the
MVTX detector and its associated services (which would be routed from only one
side, as is done in sPHENIX). Instead of having a cryotarget, we would use a
smaller vacuum chamber that could host a small solid target. The solid target
system could be similar to those used in the CLAS12 run-group D or E
experiments, which include several nuclear types in movable setup. The
lightest solid target could be beryllium, while the heaviest could be lead or
uranium oxide. For reference, the CLAS12 Silicon Verterx Tracker (SVT) inner-
most layer is located at $r$=65 mm, and is enclosed by a Faraday cage. If we
place the MVTX such that its upstream end is at the same $z$ position as the
solid target, as shown in Fig. 4, then the polar-angle acceptance of the MVTX
is $8.7^{\circ}<\theta<90^{\circ}$.

Figure 4: Top: Rendering of possible layout of sPHENIX MVTX (cyan) with the
CLAS12 SVT (green) and BMT (purple and orange). Bottom: Possible layout of the
sPHENIX MVTX and the CLAS12 SVT and BMT. This configuration would be
compatible with a solid-target.

###  II.3 Trigger rate, radiation tolerance, material budget

The sPHENIX MVTX operates at a trigger rate of 15 kHz at RHIC, which is
comparable to the CLAS12 DAQ rate. Additionally, the MAPS sensors have
undergone radiation testing up to 2 Mrad, exceeding the anticipated doses from
the sPHENIX program, and no radiation damage is expected [29], neither during
CLAS12 operation. On the other hand, the hit occupancy at CLAS12 would be much
smaller compared to RHIC running. Given the MVTX’s material budget is less
than $<0.5\%X_{0}$ per layer, we expect no detrimental impact on the CLAS12
CVT performance.

###  II.4 Triggering with the Forward Tracker

Possible triggers could be implemented using the forward tagger (FT), which
was designed to measure small-angle scattering to access the the small-$Q^{2}$
regime of electro-production ($0.01<Q^{2}<0.1$). Nominally, the kinematic
range of the FT is $2.5^{\circ}<\theta<4.5^{\circ}$ for the polar angle [30]
and it has an energy range of 0.5 to 4.5 GeV. Therefore, the virtual-photon
energy range in this proposed experiment is bound from above by the beam
energy minus the minimum energy detectable for the scattered electron, and
from below by the $\Lambda_{c}^{+}\bar{D}^{0}$ threshold. That is,
$8.7<\nu<10.1$ GeV.

##  III Observables and Analysis Methods

The physics observable in this analysis will be the cross section of the
$\gamma^{*}p\rightarrow\Lambda_{c}^{+}\bar{D}^{(*)0}$ reaction. We will not
distinguish in this analysis between events in which the $\bar{D}^{0}$ is
directly produced and those in which it is from the decay of a $\bar{D}^{*0}$.
If the measured cross section is large enough, we will divide our data sample
into bins in the virtual photon energy, $\nu$.

To measure these cross sections, we will select events with a scattered
electron in the FT and candidate of the following charmed hadron decay modes:

$\Lambda_{c}^{+}\rightarrow K^{-}\pi^{+}p\,\,{(\rm B.R.=6.28\pm 0.32\%)},$ (2)

and

$\bar{D}^{0}\rightarrow K^{+}\pi^{-}\,\,{(\rm B.R.=3.88\pm 0.05\%)}.$ (3)

We choose these decays modes because they have a small number of total
particles in the final state, all of which are charged, and have relatively
large branching ratios.

To reduce background, we will require a cut on the $z$ position of the decay
vertex of the charmed-hadron candidate, $v_{z}$, as obtained using the
MVTX111As an alternative, if there are also prompt particles measured in this
reaction, it may be possible to cut on the difference in $v_{z}$ between the
prompt particles and the displaced vertex.. We will further reduce background
by using a “bump-hunt” technique on the invariant-mass distribution of the
remaining candidates. That is, we will fit this distribution to a polynomial
(representing any background that remains after the displaced-vertex cut) plus
a Gaussian (representing the signal from the charmed particle decay).

The cross section will then be determined as

$\sigma_{\gamma p\rightarrow\Lambda_{c}^{+}\bar{D}^{(*)0}}=\frac{N_{\rm
fit}}{\ell f_{ep/\gamma p}\epsilon}$ (4)

where $N_{\rm fit}$ is the signal yield from the polynomial+Gaussian fit,
$\ell$ is the luminosity, $f_{ep/\gamma p}$ is the conversion factor from
quasi-real photoproduction222That is, $ep$ scattering at low $Q^{2}$ to real
photoproduction, and $\epsilon$ is the overall detection efficiency (which
includes acceptance effects, detector efficiency, and event-selection cuts)
which will be determined using Monte-Carlo simulations.

##  IV Estimated Reach

In this section, we provide a rough estimation of the experimental reach for
the proposed measurement. These estimates will need to be further refined by
future studies using Geant simulations and existing CLAS12 data.

###  IV.1 Total expected cross section

Du et al. predicted the cross sections for the $\Lambda_{c}^{+}\bar{D}^{0}$
and $\Lambda_{c}^{+}\bar{D}^{*0}$ and presented the results in Ref. [21] with
two different values of the model parameter $\eta$. These two estimates of the
cross section differ by a factor of $\approx$4\. We consider the lower
estimate of the cross section (corresponding to $\eta=0.5$) to be more
realistic, because it is consistent with the experimental upper limit of 94 nb
at a 90% confidence level for total charm production determined by SLAC with a
10.5 GeV photon beam [25]. For comparison, the sum of the cross sections for
$\bar{D}^{0}$ and $\bar{D}^{*0}$ channels in Du. et al. is about 90 nb. We
will therefore base our estimates here on the $\eta=0.5$ calculations.

The cross section for quasi-photoproduction (that is, electro-production with
$Q^{2}\approx 0$) is related to that of real photoproduction by

$\sigma_{ep}=\int^{y_{\rm max}}_{y_{\rm min}}\frac{\alpha}{\pi
y}\sigma_{\gamma p}(\nu)\left((1-y+1/2y^{2})\log\left(\frac{Q^{2}_{\rm
max}}{Q^{2}_{\rm min}}\right)+m_{e}^{2}y^{2}(Q^{-2}_{\rm max}-Q^{-2}_{\rm
min})\right)$ (5)

where $y=\nu/E_{\rm beam}$, $y_{\rm min}$ is evaluated at the threshold value
of $\nu$ and $y_{\rm max}$ is determined by the minimum detectable scattered-
electron energy. The limits on $Q^{2}$ for a given $y$ are given by $4E_{\rm
beam}^{2}(1-y)\sin{\theta^{e}_{\rm min}}$ and $4E_{\rm
beam}^{2}(1-y)\sin{\theta^{e}_{\rm max}}$, where the limits on $\theta_{e}$
are determined by the acceptance of the FT (2.5∘ to 4.5∘).

This evaluates to $\approx$0.0046 nb with $\bar{D}^{0}$ and $\approx$0.0036 nb
with $\bar{D}^{*0}$, which combined is $\approx$0.0082 nb.

Since similar reactions on neutrons (e.g $\gamma
n\rightarrow\Lambda_{c}^{+}D^{-}$) are expected to be at least an order of
magnitude less than those on protons [27], the per-nucleon cross section would
be about $Z/N$ times smaller than the free-proton cross-section. This
evaluates to a factor of 4/9$\approx$0.44 for 9Be.

###  IV.2 Luminosity

To provide ample luminosity while simultaneously preventing the target foil
from being so thick that charmed hadrons would decay before exiting the
target, we could use a multi-foil target, as was done in Run-Group M with a
multi-foil carbon target. Using a 5-foil Be target with 100 $\mu$m for each
foil and an 85 nA beam would correspond to 3.0$\times$1034 cm-2s-1. For
reference, in the currently-running Run-Group E experiment at CLAS12, the
luminosity for solid-target production runs are 1.0$\times$1035 cm-2s-1 for
carbon (1.5 mm thick foil at 85 nA) and 4.3$\times$1034 cm-2s-1 for lead (143
$\mu$m thick target with 70 nA).

100 days of running at $3.0\times 10^{35}$ cm-2s-1 and PAC efficiency of 50%
corresponds to 1.62$\times 10^{8}$ nb-1 of luminosity. Multiplying this by the
cross sections in the previous section (and including a factor of 0.44 for the
proton fraction) yields $\approx$270k $\Lambda_{c}^{+}\bar{D}^{0}$ events and
$\approx$210k $\Lambda_{c}^{+}\bar{D}^{*0}$ events, which combined is
$\approx$470k events.

###  IV.3 Monte-Carlo Simulations

To estimate the number of events in which either the $\Lambda_{c}^{+}$ or
$\bar{D}^{0}$ can be measured through their decays, we first ran MC
simulations of $ep\rightarrow e^{\prime}\Lambda_{c}^{+}\bar{D}^{0}$ channel,
in which the electron kinematic distributions correspond to Eq. 5. The
$\Lambda_{c}^{+}\bar{D}^{0}$ pairs were then produced with a uniform
distribution in phase space given the combined four momentum of the virtual
photon and proton. We then allowed the simulated $\bar{D}^{0}$ to decay
isotropically into a $K^{+}\pi^{-}$ pair, with the vertex-position given by an
exponential distribution, taking into consideration the lifetime of the
$\bar{D}^{0}$ and time dilation. We did the same for the $\Lambda_{c}^{+}$,
with the $K^{-}\pi^{+}p$ being generated with uniform probability within the
3-particle phase space. The resulting momentum distributions for these
simulated events are shown in Fig. 5.

Figure 5: Top row: longitudinal (left) and transverse (right) momenta
distributions for the generated charmed hadrons. Bottom row: same, for their
daughter particles

###  IV.4 Estimation of efficiency and acceptance

Assuming that there is a combined detection efficiency and acceptance of
around 80% for each of the hadrons in the forward detector, and a similar
efficiency for the electrons in the FT, approximately $(80\%)^{3}\approx 52\%$
($(80\%)^{4}\approx 41\%$) of the events with $e^{\prime}K^{+}\pi^{-}$
($e^{\prime}K^{-}\pi^{+}p$) in their final state will have all of these
particles reconstructed. We will further refine these estimates of the event-
reconstruction with using CLAS12’s detector-response simulator package, GEMC.

###  IV.5 Geometric acceptance of the MVTX

To estimate the acceptance of the MVTX, we used the generated event sample
described above. In principle, determining the decay position of a charmed
hadron requires at least one of its decay products to be within the proposed,
nominal acceptance of MVTX at CLAS12: $8.7^{\circ}<\theta<90^{\circ}$.
However, as an alternative to reduce backgrounds from poorly reconstructed
single tracks, it is possible to require at least two of the decay products to
be reconstructed in the MVTX, or in the case of the $\Lambda_{c}^{+}$ decay,
all three of the daughter particle candidates. We show the overall geometric
acceptance of the MVTX (that is the fraction of the generated events which a
requisite number of the decay products are in the MVTX’s geometric acceptance)
of each of these scenarios in Fig. 6. Almost all of the events have at least
one daughter particle in the MVTX’s acceptance. Even in the most strict
requirements (requiring all three daughter particles from the
$\Lambda^{+}_{c}$ in the MVTX acceptance) would retain over 40% of the events.

Figure 6: Overall geometric acceptance of the MVTX for detecting at least one
of the daughter particles (dashed curves), at least two daughter particles
(dotted curves) and all of the daughter particles (solid curves) for
$\Lambda^{+}_{c}$ (blue) and $\bar{D}^{0}$ (orange).

###  IV.6 MVTX efficiency

We estimate an 80% efficiency for reconstructing each daughter particle in the
MVTX, leading to $(80\%)^{3}\approx 51\%$ efficiency for the $K^{-}\pi^{+}p$
decay and $(80\%)^{3}\approx 64\%$ for the $K^{+}\pi^{-}$ channel, for events
where all of the daughter particles are in the geometric acceptance of the
MVTX. A more precise estimate of this efficiency can be determined through
future studies with Geant simulations.

###  IV.7 Event retention after displaced-vertex cut

To estimate how the thickness of the target would affect the efficiency of a
displaced-vertex cut, we used the event-generator simulations described above.
The resolution for the vertex position of a track can depend on several
factors including the magnetic field, the polar angle of the track, and the
transverse momentum of the particle. This will need to determined through
further studies with Geant simulations. In this exercise, we choose to use a
conservative cut on $v_{z}$ at 250 $\mu$m from the downstream face of the
target foil. The efficiency of this cut can be calculated as:

$\epsilon_{h}(v_{z,\rm cut})=\frac{N(v^{h}_{z}>v_{z,\rm cut})}{N_{\rm tot}}$
(6)

where $N(v_{z}>v_{z,\rm cut})$ is the number of events where the reconstructed
decay position of one of the charmed hadrons, $v^{h}_{z}$, (where the $h$
index represents either $\Lambda_{c}^{+}$ or $\bar{D}^{0}$), is greater than
the cutoff, $v_{z,\rm cut}$. The $v^{h}_{z}$ for each event is given by

$v^{h}_{z}=v^{h,\rm gen}_{z}+v^{e}_{z}$ (7)

where $v^{h,\rm gen}_{z}$ is the $z$ position of the charmed-hadron decay from
the event generator ($i.e.$, relative to the electron vertex), and $v^{e}_{z}$
is the electron vertex, which assigned uniformly to each event between $-t$
and $0$, where $t$ is the thickness of the foil.

The resulting cut efficiency, as a function of the foil thickness, is shown in
Fig. 7. With 100 $\mu$m foils, about 12% of $\Lambda_{c}^{+}$s and 34% of
$\bar{D}^{0}$s decay after the cutoff. For reference, the CLAS12 run-group E
experiment (on-going at the time of writing this letter of intent) uses a Pb
target that is 143 $\mu$m thick.

We intend to follow up these estimates with more refined tracking studies
using realistic field maps provided by the CLAS12 magnet and Kalman-Filter
reconstruction.

Figure 7: Efficiency for a displaced-vertex cut at 250 $\mu$m for the
$\Lambda_{c}^{+}$ (blue) and $\bar{D}_{0}$ (orange) channels respectively. For
reference, the expected distance these particles travel is 130 (260) $\mu$m
for $\Lambda_{c}^{+}$ ($\bar{D}^{0}$) at the mode energy, 4.9 (3.9) GeV.

###  IV.8 Expected sample size and reach

To estimate the number of events that can be measured for a given sample, we
multiplied the total number of expected events by the branching ratio for a
given channel, times the CLAS12 overall efficiency, the geometric acceptance
of the MVTX, and the event retention rate of the displaced vertex cut, as
detailed in the previous subsections. This yields, as a conservative estimate,
340 events with a reconstructed $\Lambda_{c}^{+}$ candidate and 1.6k events
with a $\bar{D}^{0}$ candidate. The factors that go into these calculations
are summarized in Table 1.

Quantity | $K^{-}\pi^{+}p$ | $K^{+}\pi^{-}$ |  notes
---|---|---|---
free-proton cross-section | 0.0082 nb |  $\sigma_{\gamma p}$ calculated from Ref. [21], $\eta=0.5$, converted to $\sigma_{ep}$ (Eq. 5)
$Z/N$ | 0.44 |  evaluated for 9Be
Tot. luminosity | 1.3$\times 10^{8}$ nb-1 |  100 days, 50% PAC efficiency, 1035 cm-2s-1, achieved with 5-foil, 100 $\mu$m Be target at 85 nA; evaluated per nucleon
Branching ratio | 6.26% | 3.88% |  from PDG
CLAS12 efficiency | 41% | 51% |  assuming 80% per detected particle
MVTX acceptance | 45% | 76% |  all daughter particles in MVTX
MVTX efficiency | 51% | 64% |  assume 80% reconstruction efficiency per daughter particle
$v_{z}$ cut | 12% | 34% |  assuming 100 $\mu$m per foil, 250 $\mu$m cut
Tot. expected signal events | 340 | 1600 |
Table 1: Factors and assumptions that go into the calculations for the total
expected yields (bottom row).

We have not studied background rates, as it heavily relies upon the
background-rejection power of the vertex-position cuts, which requires
detailed tracking studies with Geant simulations. These are outside the scope
of this Letter of Intent.

##  V Summary and Conclusions

The inclusion of measurements on open-charm production at JLab would
complement the existing $J/\psi$ program, offering valuable insights into
reaction mechanisms. Direct measurements of channels such as $\gamma
p\to\bar{D}^{0}\Lambda_{c}$ and $\gamma p\to\bar{D}^{*}\Lambda_{c}$ would
contribute to constraining the $J/\psi$ reaction mechanisms, shedding light on
whether the open-charm coupled channel mechanism [21] plays a significant role
in the observed $J/\psi$ cross-sections. This constraint is crucial for a
nuanced interpretation of $J/\psi$ data, challenging the commonly used vector-
meson dominant model employed for extracting gravitational form factors of the
nucleon.

To execute this program, the conclusion of operations for sPHENIX MVTX post-
RHIC shutdown offers a promising opportunity. Using its capability to offer
clear D-meson tagging via displaced vertex signatures, we suggest
incorporating the sPHENIX MVTX geometry into the CLAS12 tracker. This
integration, dependent on removing the standard vacuum scattering chamber and
cryotarget, would involve installing a smaller vacuum chamber to accommodate a
small solid target that would consist of multiple foils each
$\approx$100$\mu$m thick.

The use of light solid targets like beryllium or carbon, with appropriate
modeling, holds the potential to constrain corresponding cross-sections on a
proton target. Additionally, an inclusive D-meson production program with
light and heavy nuclear targets such as lead or uranium-oxide could provide
insights into cold-nuclear matter effects with charm quarks, which could
complement ongoing light-quark studies at JLab [31, 32]. All of these could
complement and pave the way for proposed charm studies at the Electron-Ion
Collider [33] and JLab at 22 GeV [34].

We intend to follow up this LOI with detailed Geant detector simulations,
encompassing signals and backgrounds, as well as thorough technical
assessments of operating conditions in CLAS12, or other detector at JLab.

## References

  * Kharzeev  _et al._ [1999] D. Kharzeev, H. Satz, A. Syamtomov, and G. Zinovjev, J / psi photoproduction and the gluon structure of the nucleon, Eur. Phys. J. C 9, 459 (1999), arXiv:hep-ph/9901375 .
  * Brodsky  _et al._ [2001] S. J. Brodsky, E. Chudakov, P. Hoyer, and J. M. Laget, Photoproduction of charm near threshold, Phys. Lett. B 498, 23 (2001), arXiv:hep-ph/0010343 .
  * Mamo and Zahed [2020] K. A. Mamo and I. Zahed, Diffractive photoproduction of $J/\psi$ and $\Upsilon$ using holographic QCD: gravitational form factors and GPD of gluons in the proton, Phys. Rev. D 101, 086003 (2020), arXiv:1910.04707 [hep-ph] .
  * Guo  _et al._ [2021] Y. Guo, X. Ji, and Y. Liu, QCD Analysis of Near-Threshold Photon-Proton Production of Heavy Quarkonium, Phys. Rev. D 103, 096010 (2021), arXiv:2103.11506 [hep-ph] .
  * Kharzeev [2021] D. E. Kharzeev, Mass radius of the proton, Phys. Rev. D 104, 054015 (2021), arXiv:2102.00110 [hep-ph] .
  * Mamo and Zahed [2022] K. A. Mamo and I. Zahed, J/$\psi$ near threshold in holographic QCD: A and D gravitational form factors, Phys. Rev. D 106, 086004 (2022), arXiv:2204.08857 [hep-ph] .
  * Wang  _et al._ [2023] X.-Y. Wang, F. Zeng, and Q. Wang, Gluon gravitational form factors of protons from charmonium photoproduction*, Chin. Phys. C 47, 074101 (2023), arXiv:2208.03186 [hep-ph] .
  * Guo  _et al._ [2023] Y. Guo, X. Ji, Y. Liu, and J. Yang, Updated analysis of near-threshold heavy quarkonium production for probe of proton’s gluonic gravitational form factors, Phys. Rev. D 108, 034003 (2023), arXiv:2305.06992 [hep-ph] .
  * Dudek  _et al._ [2012] J. Dudek _et al._ , Physics Opportunities with the 12 GeV Upgrade at Jefferson Lab, Eur. Phys. J. A 48, 187 (2012), arXiv:1208.1244 [hep-ex] .
  * Joosten and Meziani [2018] S. Joosten and Z. E. Meziani, Heavy Quarkonium Production at Threshold: from JLab to EIC, PoS QCDEV2017, 017 (2018), arXiv:1802.02616 [hep-ex] .
  * Ali  _et al._ [2019] A. Ali _et al._ (GlueX), First Measurement of Near-Threshold J/$\psi$ Exclusive Photoproduction off the Proton, Phys. Rev. Lett. 123, 072001 (2019), arXiv:1905.10811 [nucl-ex] .
  * Adhikari  _et al._ [2023] S. Adhikari _et al._ (GlueX), Measurement of the J/$\psi$ photoproduction cross section over the full near-threshold kinematic region, Phys. Rev. C 108, 025201 (2023), arXiv:2304.03845 [nucl-ex] .
  * Duran  _et al._ [2023] B. Duran _et al._ , Determining the gluonic gravitational form factors of the proton, Nature 615, 813 (2023), arXiv:2207.05212 [nucl-ex] .
  * Newton [2021] J. Newton,  _$J/\psi$ Photoproduction Near Threshold With CLAS12_, Ph.D. thesis, Old Dominion U. (main), Old Dominion U. (2021).
  * Tyson [2023] R. Tyson,  _$J/\psi$ Near-Threshold Photoproduction off the Proton and Neutron with CLAS12_, Ph.D. thesis, University of Glasgow, Glasgow U. (2023).
  * Arrington  _et al._ [2023] J. Arrington _et al._ (Jefferson Lab SoLID), The solenoidal large intensity device (SoLID) for JLab 12 GeV, J. Phys. G 50, 110501 (2023), arXiv:2209.13357 [nucl-ex] .
  * Gryniuk and Vanderhaeghen [2016] O. Gryniuk and M. Vanderhaeghen, Accessing the real part of the forward $J/\psi$-p scattering amplitude from $J/\psi$ photoproduction on protons around threshold, Phys. Rev. D 94, 074001 (2016), arXiv:1608.08205 [hep-ph] .
  * Strakovsky  _et al._ [2020] I. Strakovsky, D. Epifanov, and L. Pentchev, J/$\psi$p scattering length from GlueX threshold measurements, Phys. Rev. C 101, 042201 (2020), arXiv:1911.12686 [hep-ph] .
  * Pentchev and Strakovsky [2021] L. Pentchev and I. I. Strakovsky, $J/\psi$-$p$ Scattering Length from the Total and Differential Photoproduction Cross Sections, Eur. Phys. J. A 57, 56 (2021), arXiv:2009.04502 [hep-ph] .
  * Wang  _et al._ [2022] X.-Y. Wang, F. Zeng, and I. I. Strakovsky, $\psi$(*)p scattering length based on near-threshold charmonium photoproduction, Phys. Rev. C 106, 015202 (2022), arXiv:2205.07661 [hep-ph] .
  * Du  _et al._ [2020] M.-L. Du, V. Baru, F.-K. Guo, C. Hanhart, U.-G. Meißner, A. Nefediev, and I. Strakovsky, Deciphering the mechanism of near-threshold $J/\psi$ photoproduction, Eur. Phys. J. C 80, 1053 (2020), arXiv:2009.08345 [hep-ph] .
  * Winney  _et al._ [2023] D. Winney _et al._ (Joint Physics Analysis Center), Dynamics in near-threshold J/$\psi$ photoproduction, Phys. Rev. D 108, 054018 (2023), arXiv:2305.01449 [hep-ph] .
  * Abe  _et al._ [1984a] K. Abe _et al._ (SLAC Hybrid Facility Photon), CHARM PHOTOPRODUCTION AT 20-GeV, Phys. Rev. D 30, 1 (1984a).
  * Abe  _et al._ [1983] K. Abe _et al._ , CHARM PHOTOPRODUCTION CROSS-SECTION AT 20-GeV, Phys. Rev. Lett. 51, 156 (1983).
  * Abe  _et al._ [1984b] K. Abe _et al._ (SLAC Hybrid Facility Photon), Search for a Threshold Enhancement in the $\gamma(p)\to$ Charmed Baryon + Charmed Meson Cross-section, Phys. Rev. D 30, 694 (1984b).
  * Volk [2001] E. Volk,  _Measurement of the $D^{*\pm}$ cross-section at HERMES_, Ph.D. thesis, Hamburg U. (2001).
  * Tomasi-Gustafsson [2005] E. Tomasi-Gustafsson, Charm production in $NN$ and $\gamma N$ collisions, in  _17th International Baldin Seminar on High Energy Physics Problems: Relativistic Nuclear Physics and Quantum Chromodynamics_ , Vol. V2 (2005) pp. 231–240, arXiv:hep-ph/0411295 .
  * Adare  _et al._ [2015] A. Adare _et al._ (PHENIX), An Upgrade Proposal from the PHENIX Collaboration, (2015), arXiv:1501.06197 [nucl-ex] .
  * [29] Ming Liu et al., A Monolithic-Active-Pixel-Sensor-based Vertex Detector (MVTX) for the PHENIX Experiment at RHIC”, proposal submitted to DOE Office of Science, https://www.phenix.bnl.gov/WWW/publish/barish/publish/mxliu/sPHENIX/MVTX-Project/MVTX-Preproposal-v1.5-02012017.pdf.
  * Acker  _et al._ [2020] A. Acker _et al._ , The CLAS12 Forward Tagger, Nucl. Instrum. Meth. A 959, 163475 (2020).
  * Moran  _et al._ [2022] S. Moran _et al._ (CLAS), Measurement of charged-pion production in deep-inelastic scattering off nuclei with the CLAS detector, Phys. Rev. C 105, 015201 (2022), arXiv:2109.09951 [nucl-ex] .
  * Paul  _et al._ [2022] S. J. Paul _et al._ (CLAS), Observation of Azimuth-Dependent Suppression of Hadron Pairs in Electron Scattering off Nuclei, Phys. Rev. Lett. 129, 182501 (2022), arXiv:2207.06682 [nucl-ex] .
  * Accardi  _et al._ [2016] A. Accardi _et al._ , Electron Ion Collider: The Next QCD Frontier: Understanding the glue that binds us all, Eur. Phys. J. A 52, 268 (2016), arXiv:1212.1701 [nucl-ex] .
  * Accardi  _et al._ [2023] A. Accardi _et al._ , Strong Interaction Physics at the Luminosity Frontier with 22 GeV Electrons at Jefferson Lab, (2023), arXiv:2306.09360 [nucl-ex] .


# Approximate Carathéodory bounds via Discrepancy Theory

Victor Reis University of Washington, Seattle. Email<EMAIL_ADDRESS>Thomas
Rothvoss University of Washington, Seattle. Email<EMAIL_ADDRESS>Supported
by NSF CAREER grant 1651861 and a David & Lucile Packard Foundation
Fellowship.

###### Abstract

The approximate Carathéodory problem in general form is as follows: Given two
symmetric convex bodies $P,Q\subseteq\mathbb{R}^{m}$, a parameter
$k\in\mathbb{N}$ and $\bm{z}\in\textrm{conv}(X)$ with $X\subseteq P$, find
$\bm{v}_{1},\ldots,\bm{v}_{k}\in X$ so that
$\|\bm{z}-\frac{1}{k}\sum_{i=1}^{k}\bm{v}_{i}\|_{Q}$ is minimized. Maurey
showed that if both $P$ and $Q$ coincide with the $\|\cdot\|_{p}$-ball, then
an error of $O(\sqrt{p/k})$ is possible.

We prove a reduction to the vector balancing constant from discrepancy theory
which for most cases can provide tight bounds for general $P$ and $Q$. For the
case where $P$ and $Q$ are both $\|\cdot\|_{p}$-balls we prove an upper bound
of $\sqrt{\frac{\min\\{p,\log(\frac{2m}{k})\\}}{k}}$. Interestingly, this
bound cannot be obtained taking independent random samples; instead we use the
Lovett-Meka random walk. We also prove an extension to the more general case
where $P$ and $Q$ are $\|\cdot\|_{p}$ and $\|\cdot\|_{q}$-balls with $2\leq
p\leq q\leq\infty$.

##  1 Introduction

The (exact) Carathéodory Theorem is part of most introductory courses on the
theory of linear programming: given any vector $\bm{z}\in\textrm{conv}(X)$
where $X\subseteq\mathbb{R}^{m}$, there is a subset of points
$X^{\prime}\subseteq X$ with $|X^{\prime}|\leq m+1$ so that already
$\bm{z}\in\textrm{conv}(X^{\prime})$. More recently, the _approximate_ version
gained interest, where only $k$ vectors from $X$ may be selected with uniform
weights and the goal is to minimize the error in a given norm.

Barman [Bar15] used an approximate Carathéodory bound for algorithms to
compute approximate Nash equilibria for bimatrix games as well as for finding
$k$-densest subgraphs. The core argument of [Bar15] is as follows: if one has
two players with $n$ strategies each and some payoff matrix
$\bm{A}\in[-1,1]^{n\times n}$, then for any mixed strategy $\bm{y}$ of the
column player (i.e. $\bm{y}\in\mathbb{R}_{\geq 0}^{n}$ and $\|\bm{y}\|_{1}=1$)
one can apply the approximate Carathéodory Theorem for norm
$\|\cdot\|_{\infty}$ (or rather equivalently for $\|\cdot\|_{\log(n)}$) and
find $k:=\Theta(\frac{\log(n)}{\varepsilon^{2}})$ columns
$\bm{a}_{1},\ldots,\bm{a}_{k}$ of $\bm{A}$ so that
$\|\bm{A}\bm{y}-\frac{1}{k}\sum_{i=1}^{k}\bm{a}_{i}\|_{\infty}\leq\varepsilon$.
In other words, any mixed strategy can be $\varepsilon$-approximated by the
unweighted average of only $\Theta(\frac{\log(n)}{\varepsilon^{2}})$ many pure
strategies which then allows for an efficient enumeration. The approximate
Carathéodory Theorem has also been useful in algebraic settings. For example
Deligkas et al [DFMS22] use it to find approximate solutions to systems of
polynomial (in)equalities and Bhargava, Saraf and Volkovich [BSV20] use
approximate Carathéodory to prove that sparse polynomials have only sparse
factors which then allows efficient deterministic factorization of sparse
polynomials; both applications use the variant with respect to the
$\|\cdot\|_{\infty}$-norm.

To make the statements formal, for symmetric convex bodies
$P,Q\subseteq\mathbb{R}^{m}$ and $k\in\mathbb{N}$, we denote

$\textrm{ac}_{k}(P,Q):=\sup_{\begin{subarray}{c}X\subseteq P,\\\
\bm{z}\in\textrm{conv}(X)\end{subarray}}\inf_{\bm{v}_{1},\ldots,\bm{v}_{k}\in
X}\Big{\|}\bm{z}-\frac{1}{k}\sum_{i=1}^{k}\bm{v}_{i}\Big{\|}_{Q}$

as the best error bound with respect to the $\|\cdot\|_{Q}$-norm for
approximating a point $\bm{z}$ in the convex hull of some points in $P$. We
would like to point out that the vectors $\bm{v}_{1},\ldots,\bm{v}_{k}$ may be
taken with repetition. Here, $\|\cdot\|_{Q}$ is the norm with
$\|\bm{x}\|_{Q}=\min\\{s\geq 0\mid\bm{x}\in sQ\\}$. A folklore result is that
for the Euclidean norm one has
$\textrm{ac}_{k}(B_{2}^{m},B_{2}^{m})\leq\frac{1}{\sqrt{k}}$ for any $k\geq
1$, which gives a _dimension free_ bound. More generally, for $p\geq 1$, it is
true that $\textrm{ac}_{k}(B_{p}^{m},B_{p}^{m})\leq O(\sqrt{\frac{p}{k}})$
where $B_{p}^{m}:=\\{\bm{x}\in\mathbb{R}^{m}\mid\|\bm{x}\|_{p}\leq 1\\}$ is
the $\|\cdot\|_{p}$-unit ball. This bound is derived from Maurey’s Lemma from
functional analysis (which was reported by Pisier [Pis81]; for an English
version, see the appendix of Bourgain and Nelson [BN13]). Algorithmically, the
result is simple: write $\bm{z}=\sum_{i=1}^{N}\lambda_{i}\bm{u}_{i}$ where
$\lambda_{1},\ldots,\lambda_{N}\geq 0$ and $\sum_{i=1}^{N}\lambda_{i}=1$. Then
sample $\bm{v}_{1},\ldots,\bm{v}_{k}\in\\{\bm{u}_{1},\ldots,\bm{u}_{N}\\}$
independently according to the probabilities $\lambda_{i}$ (possibly with
repetition).

Another approach in the literature by Mirrokni et al [MLVW17] is based on the
desire to avoid the computation of
$\bm{z}=\sum_{i=1}^{N}\lambda_{i}\bm{u}_{i}$. Instead they use the _Mirror
Descent_ algorithm from convex optimization to compute the sequence
$\bm{v}_{1},\ldots,\bm{v}_{k}$ directly. In fact they reprove the bound of
$\textrm{ac}_{k}(B_{p}^{m},B_{p}^{m})\leq O(\sqrt{\frac{p}{k}})$ using their
framework. More recently, Combettes and Pokutta [CP21] show that the Frank-
Wolfe algorithm can also be used to recover the same bounds. From the current
state of the literature, there are two directions that appear natural to
follow:

  * •

_Approximate Carathéodory for general pairs of norms._ The existing bounds are
for the case where $P$ and $Q$ are the same $\|\cdot\|_{p}$-ball. Is there a
convenient framework that can handle general symmetric convex bodies or at
least $P=B_{p}^{m}$ and $Q=B_{q}^{m}$?

  * •

_Tight bounds for approximate Carathéodory._ Generally, it is stated that for
example the bound $\textrm{ac}_{k}(B_{p}^{m},B_{p}^{m})\leq
O(\sqrt{\frac{p}{k}})$ is tight (see e.g. [MLVW17]). But that is only true if
one aims for a dimension independent bound. So for which regimes of $m$ vs.
$k$ and $p$ is it possible to improve the bound?

A classical area within combinatorics that appears related to these questions
is _discrepancy theory_. Let $S_{1},\ldots,S_{m}\subseteq\\{1,\ldots,n\\}$ be
a set system over $n$ elements. Then the goal is to find a bi-coloring
$\bm{x}\in\\{-1,1\\}^{n}$ so that the worst imbalance
$\max_{i=1,\ldots,m}|\sum_{j\in S_{i}}x_{j}|$ is minimized. A seminal result
of Spencer [Spe85] says that for $m\geq n$, the discrepancy is bounded by
$O(\sqrt{n\log(\frac{2m}{n})})$. If no element is in more than $t$ sets, then
one can also prove a bound of $2t$, see Beck and Fiala [BF81]. A convex
geometry based method by Banaszczyk [Ban98] shows that for any
$\bm{A}\in\mathbb{R}^{m\times n}$ with column length $\|\bm{A}^{j}\|_{2}\leq
1$ for all $j=1,\ldots,n$ and any symmetric convex body
$K\subseteq\mathbb{R}^{m}$ with Gaussian measure at least $1/2$ (for example
$K=\Theta(\sqrt{\log(m)})\cdot B_{\infty}^{m}$ or $K=\Theta(\sqrt{m})\cdot
B_{2}^{m}$ work), there is a coloring $\bm{x}\in\\{-1,1\\}^{n}$ with
$\bm{A}\bm{x}\in 5K$. Interestingly, neither of these cited results of [Spe85,
BF81, Ban98] can be obtained by merely taking a uniform random coloring
$\bm{x}$. But for example, the result by Spencer allows for elegant
algorithmic proofs. While the first such algorithm was due to Bansal [Ban10],
we focus on the later work of Lovett and Meka [LM12] whose main claim can be
paraphrased as follows:

######  Theorem 1 ([LM12]).

Let $\bm{A}\in\mathbb{R}^{m\times n}$ and $\bm{x}_{0}\in[-1,1]^{n}$ and let
$C_{1},C_{2}>0$ be small enough constants. Then there is an efficiently
computable distribution $\pazocal{D}(\bm{A},\bm{x}_{0})$ with the following
properties:

  1. (A)

One has $|\\{j\in[n]:x_{j}\in\\{\pm 1\\}\\}|\geq\frac{n}{2}$ for all
$\bm{x}\sim\pazocal{D}(\bm{A},\bm{x}_{0})$.

  2. (B)

One has $\|\bm{A}(\bm{x}-\bm{x}_{0})\|_{\infty}\leq\Delta$ for all
$\bm{x}\sim\pazocal{D}(\bm{A},\bm{x}_{0})$ where $\Delta\geq 0$ is any
parameter satisfying
$\sum_{i=1}^{m}\exp(-C_{1}\frac{\Delta^{2}}{\|\bm{A}_{i}\|_{2}^{2}})\leq
C_{2}n$.

  3. (C)

One has
$\mathop{\mathbb{E}}_{\bm{x}\sim\pazocal{D}(\bm{A},\bm{x}_{0})}[\bm{x}]=\bm{x}_{0}$.

  4. (D)

The random vector $\bm{x}-\bm{x}_{0}$ is $O(1)$-subgaussian. In particular
${\|\left<\bm{A}_{i},\bm{x}-\bm{x}_{0}\right>\|_{\psi_{2}}\lesssim\|\bm{A}_{i}\|_{2}}$
for all $i=1,\ldots,m$.

The running time to compute a sample is111Throughout this work, we will use
$T(m,n)$ as the best running time to generate a sample from the described
distribution. Whenever we state a running time using $T(\cdot,\cdot)$ we
implicitly assume that the function $T$ is non-decreasing in $m$ and $n$ and
that $T(m,n)\geq mn$ which corresponds to the input length. $T(m,n)\leq
O(n^{1+\omega}+n^{2}m)$.

Here we use the notation $A\lesssim B$ if there is a universal constant $C>0$
so that $A\leq C\cdot B$. The statement differs in several aspects to the
original statement of [LM12]. We discuss and justify the changes in Appendix
A. Intuitively, $\pazocal{D}(\bm{A},\bm{x}_{0})$ is simply the outcome of a
_Brownian motion_ starting at $\bm{x}_{0}$ that freezes coordinates as soon as
they hit $+1$ or $-1$ and it freezes constraints if
$|\left<\bm{A}_{i},\bm{x}-\bm{x}_{0}\right>|=\Delta$. For example, if
$\bm{A}\in\\{0,1\\}^{m\times n}$ with $m\geq n$ is the incidence matrix in
Spencer’s setting, then one may choose
$\Delta:=\Theta(\sqrt{n\log(\frac{2m}{n})})$ and obtain a partial coloring of
discrepancy $\Delta$ that colors at least half the coordinates222One can then
obtain a full coloring by iterating the argument $O(\log n)$ times. In the
$i$th such iteration (with $i\geq 0$) there are at most $n/2^{i}$ elements
uncolored, so the suffered discrepancy decreases to
$O(\sqrt{(n/2^{i})\log\frac{2m}{n/2^{i}}})$. Summing over these terms gives a
convergent sum of value $O(\Delta)$..

###  1.1 Our contribution

The _vector balancing constant_ for two symmetric convex bodies
$P,Q\subseteq\mathbb{R}^{m}$ is

$\textrm{vb}(P,Q):=\sup\Big{\\{}\min_{\bm{x}\in\\{-1,1\\}^{n}}\Big{\|}\sum_{i=1}^{n}x_{i}\bm{v}_{i}\Big{\|}_{Q}\mid
n\in\mathbb{N},\bm{v}_{1},\ldots,\bm{v}_{n}\in P\Big{\\}}$

The connection between the approximate Carathéodory problem and vector
balancing was already discovered by Dadush et al [DNTT18] who proved that for
any symmetric convex bodies $P,Q\subseteq\mathbb{R}^{m}$ one has
$\textrm{ac}_{k}(P,Q)\leq\frac{\textrm{vb}(P,Q)}{k}$. But for example for
$P=Q=B_{2}^{m}$ one has $\textrm{vb}(B_{2}^{m},B_{2}^{m})=\Theta(\sqrt{m})$
and so the obtained bound is $O(\frac{\sqrt{m}}{k})$, which is suboptimal if
$k\ll m$. Instead, we suggest a reduction to a slight variant of the vector
balancing constant that allows for tight bounds. Let

$\textrm{vb}_{n}(P,Q):=\sup\Big{\\{}\min_{\bm{x}\in\\{-1,1\\}^{n}}\Big{\|}\sum_{i=1}^{n}x_{i}\bm{v}_{i}\Big{\|}_{Q}\mid\bm{v}_{1},\ldots,\bm{v}_{n}\in
P\Big{\\}}$

be the vector balancing constant restricted to exactly $n$ vectors333We should
note that this is the same as asking for _at most $n$_ vectors as $\bm{0}\in
P$.. We prove the following:

######  Theorem 2.

For any symmetric convex bodies $P,Q\subseteq\mathbb{R}^{m}$ and any
$k\in\mathbb{N}$ one has

$\textrm{ac}_{k}(P,Q)\leq 4\sum_{\ell\geq
1}\frac{1}{k2^{\ell}}\cdot\textrm{vb}_{k2^{\ell}}(P,Q)$

The vectors $\bm{v}_{1},\ldots,\bm{v}_{k}$ can be found in time $O(\log m)$
times the time to find a coloring behind $\textrm{vb}_{t}(P,Q)$ where $t\leq
m+1$, assuming we are given $\bm{z}$ as convex combination of at most $m+1$
vectors from $X$.

For most bodies the quantity $\textrm{vb}_{k}(P,Q)$ grows sublinear in $k$ and
the sum is dominated by the first term, in which case one has
$\textrm{ac}_{k}(P,Q)\lesssim\frac{1}{k}\cdot\textrm{vb}_{k}(P,Q)$. For
example if $P=Q=B_{2}^{m}$ one then has
$\textrm{vb}_{k}(B_{2}^{m},B_{2}^{m})=\Theta(\sqrt{k})$ and so one recovers
the $O(\frac{1}{\sqrt{k}})$ bound mentioned earlier444Though not all bodies
allow for such a sublinear dependence. For example fix $1\leq k\leq m/2$. Then
one has $\textrm{vb}_{k}(B_{1}^{m},B_{1}^{m})=\Theta(k)$ and so Theorem 2
provides a suboptimal bound of $\textrm{ac}_{k}(B_{1}^{m},B_{1}^{m})\leq
O(\log\frac{m}{k})$. On the other hand, indeed it is true that
$\textrm{ac}_{k}(B_{1}^{m},B_{1}^{m})\geq\Omega(1)$ meaning that the
approximate Carathéodory bound does not even improve with $k$ (at least as
long as $k\leq m/2$). To see this, consider
$X:=\\{\bm{e}_{1},\ldots,\bm{e}_{m}\\}$ and a target of
$\bm{z}:=(\frac{1}{m},\ldots,\frac{1}{m})$. Then for any
$\bm{v}_{1},\ldots,\bm{v}_{k}\in X$ one has
$\|\bm{z}-\frac{1}{k}\sum_{i=1}^{k}\bm{v}_{i}\|_{1}\geq\Omega(1)$ since any
coordinate whose unit vector is not included will contribute $\frac{1}{m}$ to
the norm.. Also note that by [LSV86], for any symmetric convex bodies
$P,Q\subseteq\mathbb{R}^{m}$ and any $t\in\mathbb{N}$ one has
$\textrm{vb}_{t}(P,Q)\leq 2\textrm{vb}_{m}(P,Q)$, meaning that the worst case
is basically attained for $m$ many vectors. Then the infinite sum in Theorem 2
is dominated by the first $\log(2m/k)$ terms if $k\leq m$ and the first term
if $k\geq m$.

For balancing vectors in $B_{p}^{m}$ into $B_{q}^{m}$ we prove the following:

######  Theorem 3.

For $2\leq p\leq q\leq\infty$ and $n\leq m$ one has

$\textrm{vb}_{n}(B_{p}^{m},B_{q}^{m})\lesssim\frac{\sqrt{\min\\{p,\log(\frac{2m}{n})\\}}}{\frac{1}{2}-\frac{1}{p}+\frac{1}{q}}\cdot
n^{1/2-1/p+1/q}$

The time to find the corresponding coloring is $O(\log n)\cdot T(m,n)$.

We should point out that the upper bound on
$\textrm{vb}_{n}(B_{p}^{m},B_{q}^{m})$ itself is already proven in [RR20].
However, that argument goes via the Gaussian measure of the suitable partial
colorings and the only known algorithms are via convex optimization resulting
in large polynomial running times. In contrast, here we give a streamlined
argument that shows that the more efficient Lovett-Meka algorithm can be used
to obtain the same bound rather than relying on convex optimization.

Combining the results above then gives:

######  Theorem 4.

Let $2\leq p\leq q\leq\infty$ and $k\in\mathbb{N}$. Then

$\textrm{ac}_{k}(B_{p}^{m},B_{q}^{m})\lesssim\frac{1}{\frac{1}{2}-\frac{1}{p}+\frac{1}{q}}\cdot\frac{\sqrt{\min\\{p,\log(\frac{2m}{k})\\}}}{k^{1/2+1/p-1/q}}$

The vectors $\bm{v}_{1},\ldots,\bm{v}_{k}$ can be found in time
$O(\log^{2}m)\cdot T(m,m+1)\leq O(m^{1+\omega}\log^{2}(m))$ assuming we are
given $\bm{z}$ as a convex combination of at most $m+1$ vectors in $X$.

To the best of our knowledge this is the first approximate Carathéodory bound
for pairs of different $\|\cdot\|_{p}$-norms. In particular, when $p=q$ this
improves upon the $O(\sqrt{\frac{p}{k}})$ bound in [MLVW17] whenever
$p\ll\log(\frac{2m}{k})$:

######  Corollary 5.

Let $2\leq p\leq\infty$ and $k\in\mathbb{N}$. Then

$\textrm{ac}_{k}(B_{p}^{m},B_{p}^{m})\lesssim\sqrt{\frac{\min\\{p,\log(\frac{2m}{k})\\}}{k}}$

The vectors $\bm{v}_{1},\ldots,\bm{v}_{k}$ can be found in time
$O(\log^{2}m)\cdot T(m,m+1)\leq O(m^{1+\omega}\log^{2}(m))$ assuming we are
given $\bm{z}$ as a convex combination of at most $m+1$ vectors in $X$.

Finally, we show that the bound in Theorem 3 is tight up to a factor of
$\frac{1}{2}-\frac{1}{p}+\frac{1}{q}$:

######  Theorem 6.

Let $2\leq p\leq q\leq\infty$ and $n\leq m\leq 2^{n}$. Then

$\textrm{vb}_{n}(B_{p}^{m},B_{q}^{m})\gtrsim\sqrt{\min\Big{\\{}p,\log\Big{(}\frac{2m}{n}\Big{)}\Big{\\}}}\cdot
n^{1/2-1/p+1/q}.$

##  2 Preliminaries

In this section we review a few facts that we later rely on. Let
$S^{m-1}:=\\{\bm{x}\in\mathbb{R}^{m}\mid\|\bm{x}\|_{2}=1\\}$ be the sphere.

#### Convex functions.

Recall the following well known fact:

######  Lemma 7 (Jensen Inequality for convave functions).

Let $X$ be any $\mathbb{R}$-valued random variable and let
$F:\mathbb{R}\to\mathbb{R}$ be a concave function, then
$F(\mathop{\mathbb{E}}[X])\geq\mathop{\mathbb{E}}[F(X)]$.

#### Estimates on $\|\cdot\|_{p}$ norms.

It will be useful to understand how the norm $\|\bm{z}\|_{p}$ of a vector can
change depending on $p\in[1,\infty]$.

######  Lemma 8.

For any $\bm{z}\in\mathbb{R}^{m}$ and $1\leq p\leq q\leq\infty$ one has
$\|\bm{z}\|_{q}\leq\|\bm{z}\|_{p}\leq m^{1/p-1/q}\|\bm{z}\|_{q}$.

######  Lemma 9.

For any $\bm{z}\in\mathbb{R}^{m}$ and $1\leq p\leq q\leq\infty$, we have
$\|\bm{z}\|_{q}^{q}\leq\|\bm{z}\|_{p}^{p}\cdot\|\bm{z}\|_{\infty}^{q-p}$.

#### The subgaussian norm.

We introduce a concept from probability theory that is extremely useful and
convenient when dealing with random variables that have Gaussian-type tails.
For a random variable $X\in\mathbb{R}$ we define the _subgaussian norm_ as

$\|X\|_{\psi_{2}}:=\inf\Big{\\{}s>0:\mathop{\mathbb{E}}\Big{[}\exp\Big{(}\frac{X^{2}}{s^{2}}\Big{)}\Big{]}\leq
2\Big{\\}}$

One may think of $\|X\|_{\psi_{2}}$ as the minimum number so that the tail of
$X$ is dominated by the Gaussian $N(0,\|X\|_{\psi_{2}}^{2})$. For example if
$X\sim N(0,t^{2})$ then $\|X\|_{\psi_{2}}=\Theta(t)$ and also if
$X\sim\\{-t,t\\}$ uniformly, then $\|X\|_{\psi_{2}}=\Theta(t)$. It may not be
obvious but indeed $\|\cdot\|_{\psi_{2}}$ is a norm on the space of jointly
distributed random variables, i.e.
$\|tX\|_{\psi_{2}}=|t|\cdot\|X\|_{\psi_{2}}$ and
$\|X_{1}+X_{2}\|_{\psi_{2}}\leq\|X_{1}\|_{\psi_{2}}+\|X_{2}\|_{\psi_{2}}$ for
jointly distributed random variables $X_{1},X_{2}$ (even if they are
dependent). We will use in particular the following properties:

######  Lemma 10.

The subgaussian norm satisfies the following:

  1. (A)

For any real random variable $X$ and any $p\geq 1$ one has
$\mathop{\mathbb{E}}[|X|^{p}]^{1/p}\lesssim\sqrt{p}\cdot\|X\|_{\psi_{2}}$.

  2. (B)

If $X_{1},\ldots,X_{N}$ are independent real mean-zero random variables555The
argument also works in the Martingale setting. Suppose for any condititioning
on $X_{1},\ldots,X_{i-1}$ one has $\|X_{i}\|_{\psi_{2}}\leq L_{i}$. Then
$\|X_{1}+\cdots+X_{N}\|_{\psi_{2}}\lesssim(\sum_{i=1}^{N}L_{i}^{2})^{1/2}$.,
then

$\|X_{1}+\cdots+X_{N}\|_{\psi_{2}}\lesssim\Big{(}\sum_{i=1}^{N}\|X_{i}\|_{\psi_{2}}^{2}\Big{)}^{1/2}$

  3. (C)

For $\bm{a}\in\mathbb{R}^{m}$ and $\bm{x}\sim S^{m-1}$ uniformly one has
$\|\left<\bm{a},\bm{x}\right>\|_{\psi_{2}}\lesssim\frac{1}{\sqrt{m}}\|\bm{a}\|_{2}$.

  4. (D)

For any real random variable $X$ with $\mathop{\mathbb{E}}[X]=0$ and any
$\lambda\geq 0$ one has

$\Pr[|X|\geq\lambda\|X\|_{\psi_{2}}]\leq 2e^{-C\lambda^{2}},$

where $C>0$ is a universal constant.

We recommend the excellent textbook of Vershynin [Ver18] for details. For the
lower bound we will use the following reverse Chernoff bound from [KY15]:

######  Lemma 11.

Given independent random variables $x_{1},\dots,x_{n}\sim\\{-1,1\\}$ and
$\lambda\in[3,\sqrt{n}/2]$,

$\Pr[x_{1}+\dots+x_{n}\geq\lambda\sqrt{n}]\geq\exp(-9\lambda^{2}/2).$

##  3 Reduction from Approximate Carathéodory to Vector Balancing

In this section, we prove the reduction of the approximate Carathéodory
problem to vector balancing as stated in Theorem 2. The idea is to follow the
classical approach of [LSV86]: begin with an arbitrary convex combination and
round the coefficients bit-by-bit. The same basic approach was also followed
by Dadush et al [DNTT18]. We prove an auxiliary lemma that bounds the error
when “doubling the fractionality”.

######  Lemma 12.

Let $P,Q\subseteq\mathbb{R}^{m}$ be symmetric convex bodies and let
$\delta>0$. Let $\bm{z}=\sum_{i=1}^{n}\lambda_{i}\bm{v}_{i}$ where
$\bm{v}_{1},\ldots,\bm{v}_{n}\in P$ and $\bm{\lambda}\in\delta\mathbb{Z}_{\geq
0}^{n}$. Then there is a vector
$\bm{z}^{\prime}=\sum_{i=1}^{n}\lambda_{i}^{\prime}\bm{v}_{i}$ where
$\bm{\lambda}^{\prime}\in 2\delta\mathbb{Z}_{\geq 0}^{n}$ so that
$\|\bm{z}-\bm{z}^{\prime}\|_{Q}\leq\delta\cdot\textrm{vb}_{n}(P,Q)$ and
$\sum_{i=1}^{n}\lambda_{i}^{\prime}\leq\sum_{i=1}^{n}\lambda_{i}$.

###### Proof.

Write $\lambda_{i}=2\delta a_{i}+\delta b_{i}$ with $b_{i}\in\\{0,1\\}$ and
$a_{i}\in\mathbb{Z}_{\geq 0}$. Let $I:=\\{i\in[n]\mid b_{i}=1\\}$. Now, let
$\bm{x}\in\\{-1,1\\}^{I}$ be the coloring so that $\|\sum_{i\in
I}x_{i}\bm{v}_{i}\|_{Q}\leq\textrm{vb}_{|I|}(P,Q)\leq\textrm{vb}_{n}(P,Q)$. We
may assume that $\sum_{i\in I}x_{i}\leq 0$ — otherwise replace $\bm{x}$ with
$-\bm{x}$. We may extend the vector to $\bm{x}\in\\{-1,0,1\\}^{m}$ by setting
$x_{i}:=0$ for $i\notin I$. We update $\lambda_{i}^{\prime}:=2\delta
a_{i}+\delta(1+x_{i})b_{i}\in 2\delta\mathbb{Z}_{\geq 0}$ for $i\in[n]$. Next,
we define $\bm{z}^{\prime}:=\sum_{i=1}^{n}\lambda_{i}^{\prime}\bm{v}_{i}$.
Then

$\|\bm{z}-\bm{z}^{\prime}\|_{Q}=\delta\Big{\|}\sum_{i\in
I}x_{i}\bm{v}_{i}\Big{\|}_{Q}\leq\delta\cdot\textrm{vb}_{n}(P,Q)$

Note that $\sum_{i\in I}x_{i}\leq 0$ implies that
$\sum_{i=1}^{n}\lambda_{i}^{\prime}\leq\sum_{i=1}^{n}\lambda_{i}$. This gives
the claim. ∎

Next, we iteratively apply Lemma 12 to an initial convex combination until the
convex coefficients are multiples of $\frac{1}{k}$. We almost obtain the
desired claim, just that the number of vectors might be _less_ than $k$.

######  Lemma 13.

Let $P,Q\subseteq\mathbb{R}^{m}$ be symmetric convex bodies. Then for any
$\bm{z}\in\textrm{conv}(X)$ with $X\subseteq P$ and $k\in\mathbb{N}$ there are
$s\in\\{0,\ldots,k\\}$ and $\bm{v}_{1},\ldots,\bm{v}_{s}\in X$ so that

$\Big{\|}\bm{z}-\frac{1}{k}\sum_{i=1}^{s}\bm{v}_{i}\Big{\|}_{Q}\leq\sum_{\ell\geq
1}\frac{2}{k2^{\ell}}\cdot\textrm{vb}_{k2^{\ell}}(P,Q)$

The vectors can be found in time $O(\log m)$ times the time to find the
colorings in $\textrm{vb}_{t}(P,Q)$ where $t\leq m+1$.

###### Proof.

Fix a point $\bm{z}\in\textrm{conv}(X)$ where $X\subseteq P$. Then we can
write $\bm{z}=\sum_{i=1}^{n}\lambda_{i}\bm{v}_{i}$ where $n\leq m+1$,
$\bm{v}_{1},\ldots,\bm{v}_{n}\in X$, $\lambda_{i}\geq 0$ for all
$i=1,\ldots,m$ and $\sum_{i=1}^{m}\lambda_{i}=1$. Without loss of generality
we may assume that $\bm{\lambda}\in\frac{2^{-L}}{k}\mathbb{Z}_{\geq 0}^{n}$
for some $L\in\mathbb{N}$. We abbreviate $\bm{z}^{(L)}:=\bm{z}$. Now suppose
for $\ell\in\\{0,\ldots,L\\}$ the current iterate is $\bm{z}^{(\ell)}$ so that
$\bm{z}^{(\ell)}=\sum_{i=1}^{n}\lambda_{i}^{(\ell)}\bm{v}_{i}$ and
$\bm{\lambda}^{(\ell)}\in\frac{2^{-\ell}}{k}\mathbb{Z}_{\geq 0}^{n}$.

Then we apply Lemma 12 to obtain a vector
$\bm{z}^{(\ell-1)}=\sum_{i=1}^{n}\lambda_{i}^{(\ell-1)}\bm{v}_{i}$ with
$\bm{\lambda}^{(\ell-1)}\in\frac{2^{-(\ell-1)}}{k}\mathbb{Z}_{\geq 0}^{n}$ and
$\sum_{i=1}^{n}\lambda_{i}^{(\ell-1)}\leq 1$. Using that
$|\textrm{supp}(\bm{\lambda}^{(\ell)})|\leq k2^{\ell}$, the approximation
error satisfies

$\big{\|}\bm{z}^{(\ell)}-\bm{z}^{(\ell-1)}\big{\|}_{Q}\leq\frac{1}{2^{\ell}k}\cdot\textrm{vb}_{|\textrm{supp}(\bm{\lambda}^{(\ell)})|}(P,Q)\leq\frac{1}{2^{\ell}k}\cdot\textrm{vb}_{k2^{\ell}}(P,Q)$

Note that the final iterate is of the form
$\bm{z}^{(0)}=\sum_{i=1}^{n}\lambda^{(0)}_{i}\bm{v}_{i}$ with
$\lambda_{i}^{(0)}\in\frac{\mathbb{Z}_{\geq 0}}{k}$ and
$\sum_{i=1}^{n}\lambda_{i}^{(0)}\leq 1$. Then for
$s:=k\sum_{i=1}^{n}\lambda_{i}^{(0)}\in\\{0,\ldots,k\\}$, let
$\bm{u}_{1},\ldots,\bm{u}_{s}$ be a list of vectors that contains $\bm{v}_{i}$
exactly $k\lambda_{i}^{(0)}\in\mathbb{Z}_{\geq 0}$ times. Using the triangle
inequality we obtain

$\Big{\|}\bm{z}-\frac{1}{k}\sum_{i=1}^{s}\bm{u}_{i}\Big{\|}_{Q}\leq\sum_{\ell=1}^{L}\|\bm{z}^{(\ell)}-\bm{z}^{(\ell-1)}\|_{Q}\leq\sum_{\ell\geq
1}\frac{1}{k2^{\ell}}\cdot\textrm{vb}_{k2^{\ell}}(P,Q)$

Now let us discuss the running time. First, we can choose $L\leq O(\log m)$
while possibly making a rounding error of $\max\\{\|\bm{y}\|_{Q}:\bm{y}\in
P\\}\leq\textrm{vb}_{1}(P,Q)$, which we absorb by paying an extra factor of 2.
Then the running time is dominated by the time to find the colorings. Note
that we call $\textrm{vb}_{t}(P,Q)$ only $L$ times for parameters $t$ with
$t\leq m+1$. ∎

Now we will use the same trick as Dadush et al [DNTT18] in order to obtain
exactly $k$ vectors, at the expense of a factor 2 in the approximation error:

###### Proof of Theorem 2.

Let $\bm{z}\in\textrm{conv}(X)$ where $X\subseteq P$. Fix a vector
$\bm{u}_{0}\in X$ and write $X^{\prime}:=\\{\bm{u}-\bm{u}_{0}\mid\bm{u}\in
X\\}$. Note that in particular $\bm{0}\in X^{\prime}$ and
$\bm{z}-\bm{u}_{0}\in\textrm{conv}(X^{\prime})$. We apply Lemma 13 and obtain
vectors $\bm{v}_{1},\ldots,\bm{v}_{s}\in X^{\prime}$ with $s\leq k$ so that

$\Big{\|}(\bm{z}-\bm{u}_{0})-\frac{1}{k}\sum_{i=1}^{s}\bm{v}_{i}\Big{\|}_{Q}\leq\sum_{\ell\geq
1}\frac{2}{k2^{\ell}}\cdot\textrm{vb}_{k2^{\ell}}(2P,Q)$

using that $X^{\prime}\subseteq 2P$. Since $\bm{0}\in X^{\prime}$, we can
extend this sequence to a list $\bm{v}_{1},\ldots,\bm{v}_{k}$ of $k$ vectors.
Each $\bm{v}_{i}\in X^{\prime}$ can be written as
$\bm{v}_{i}=\bm{u}_{i}-\bm{u}_{0}$ with $\bm{u}_{1},\ldots,\bm{u}_{k}\in X$.
Then

$\Big{\|}\bm{z}-\frac{1}{k}\sum_{i=1}^{k}\bm{u}_{k}\Big{\|}_{Q}=\Big{\|}(\bm{z}-\bm{u}_{0})-\frac{1}{k}\sum_{i=1}^{k}(\bm{u}_{k}-\bm{u}_{0})\Big{\|}_{Q}\leq
4\sum_{\ell\geq 1}\frac{1}{k2^{\ell}}\cdot\textrm{vb}_{k2^{\ell}}(P,Q).\qed$

##  4 Vector balancing from $B_{p}^{m}$ to $B_{q}^{m}$

From now on, we focus on the case where $P=B_{p}^{m}$ and $Q=B_{q}^{m}$.

###  4.1 Balancing from $B_{p}^{m}$ to $B_{p}^{m}$

Suppose we have a matrix $\bm{A}\in\mathbb{R}^{m\times n}$ with
$\bm{A}^{1},\ldots,\bm{A}^{n}\in B_{p}^{m}$. Then for a uniform random
$\bm{x}\in\\{-1,1\\}^{n}$ one has
$\mathop{\mathbb{E}}[\|\bm{A}\bm{x}\|_{p}]\lesssim\sqrt{pn}$. This result
extends to the case where $\bm{x}$ is subgaussian rather than independent.

######  Lemma 14.

Let $\bm{A}^{1},\ldots,\bm{A}^{n}\in B_{p}^{m}$ for $p\geq 2$ and let
$\bm{x}_{0}\in[-1,1]^{n}$. Then

$\mathop{\mathbb{E}}_{\bm{x}\sim\pazocal{D}(\bm{A},\bm{x}_{0})}[\|\bm{A}(\bm{x}-\bm{x}_{0})\|_{p}]\lesssim\sqrt{pn}.$

###### Proof.

It will be convenient to abbreviate $\bm{B}\in\mathbb{R}^{m\times n}$ as the
matrix with entries $B_{ij}:=A_{ij}^{2}$. Then we have

$\displaystyle\mathop{\mathbb{E}}_{\bm{x}\sim\pazocal{D}(\bm{A},\bm{x}_{0})}[\|\bm{A}(\bm{x}-\bm{x}_{0})\|_{p}]$
$\displaystyle\stackrel{{\scriptstyle(*)}}{{\leq}}$
$\displaystyle\mathop{\mathbb{E}}_{\bm{x}\sim\pazocal{D}(\bm{A},\bm{x}_{0})}\big{[}\|\bm{A}(\bm{x}-\bm{x}_{0})\|_{p}^{p}\big{]}^{1/p}$
$\displaystyle=$
$\displaystyle\Big{(}\sum_{i=1}^{m}\mathop{\mathbb{E}}_{\bm{x}\sim\pazocal{D}(\bm{A},\bm{x}_{0})}\big{[}|\left<\bm{A}_{i},\bm{x}-\bm{x}_{0}\right>|^{p}\big{]}\Big{)}^{1/p}$
$\displaystyle\stackrel{{\scriptstyle\textrm{Thm~{}\ref{thm:LovettMekaRephrased}.(D)+Lem~{}\ref{lem:PropertiesOfSubgaussianNorm}.(A)}}}{{\lesssim}}$
$\displaystyle\Big{(}\sum_{i=1}^{m}\big{(}\sqrt{p}\cdot\|\bm{A}_{i}\|_{2}\big{)}^{p}\Big{)}^{1/p}$
$\displaystyle=$
$\displaystyle\sqrt{p}\cdot\sum_{i=1}^{m}\Big{(}\sum_{j=1}^{n}A_{ij}^{2}\Big{)}^{p/2}\Big{)}^{1/p}$
$\displaystyle=$
$\displaystyle\sqrt{p}\cdot\Big{(}\Big{(}\sum_{i=1}^{m}\Big{(}\sum_{j=1}^{n}B_{ij}\Big{)}^{p/2}\Big{)}^{2/p}\Big{)}^{1/2}$
$\displaystyle=$
$\displaystyle\sqrt{p}\cdot\Big{(}\Big{\|}\sum_{j=1}^{n}\bm{B}^{j}\Big{\|}_{p/2}\Big{)}^{1/2}$
$\displaystyle\stackrel{{\scriptstyle\textrm{triangle ineq.}}}{{\leq}}$
$\displaystyle\sqrt{p}\cdot\Big{(}\sum_{j=1}^{n}\underbrace{\|\bm{B}^{j}\|_{p/2}}_{\leq
1}\Big{)}^{1/2}\stackrel{{\scriptstyle(**)}}{{\leq}}\sqrt{p}\cdot\sqrt{n}.$

Here we are using Jensen’s Inequality (Lemma 7) with the concavity of
$f(z)=z^{1/p}$ in $(*)$. Finally in $(**)$ we have made use of

$\|\bm{B}^{j}\|_{p/2}=\Big{(}\sum_{i=1}^{m}(A_{ij}^{2})^{p/2}\Big{)}^{2/p}=\Big{(}\underbrace{\sum_{i=1}^{m}|A_{ij}|^{p}}_{\leq
1}\Big{)}^{2/p}\leq 1.$

This shows the claim. ∎

###  4.2 A dimension-free upper bound on $\|\cdot\|_{\infty}$

Now suppose we have a matrix $\bm{A}\in\mathbb{R}^{m\times n}$ with
$\bm{A}^{1},\ldots,\bm{A}^{n}\in B_{p}^{m}$ and we want to find a coloring
$\bm{x}$ with small value of $\|\bm{A}\bm{x}\|_{\infty}$. If we were to take a
random coloring and the matrix happens to contain a row of all-ones, then in
expectation one would have $\|\bm{A}\bm{x}\|_{\infty}\gtrsim\sqrt{n}$. It
turns out that the Lovett-Meka distribution improves significantly over this
bound. However, obtaining a bound solely dependent on $n$ is slightly delicate
since the Euclidean norm bound of $\|\bm{A}^{j}\|_{2}\leq m^{1/2-1/p}$ on the
columns might be tight.

######  Lemma 15.

Let $p\geq 2$, $\bm{x}_{0}\in[-1,1]^{n}$ and let $\bm{A}^{m\times n}$ be a
matrix with $\|\bm{A}^{j}\|_{p}\leq 1$ for all $j=1,\ldots,n$. Then for any
$\bm{x}\sim\pazocal{D}(\bm{A},\bm{x}_{0})$ one has
$\|\bm{A}(\bm{x}-\bm{x}_{0})\|_{\infty}\lesssim\sqrt{p}\cdot n^{1/2-1/p}$.

###### Proof.

The goal is to verify that the condition in Theorem 1.(B) applies for a value
of $\Delta$ that is of the order $\sqrt{p}\cdot n^{1/2-1/p}$. First we convert
the bound on the $\|\cdot\|_{p}$-norm of the columns $\bm{A}^{j}$ into
information about the $\|\cdot\|_{2}$-norm of the rows $\bm{A}_{i}$. In
particular one has

$\Big{(}\frac{1}{n}\sum_{i=1}^{m}\|\bm{A}_{i}\|_{2}^{p}\Big{)}^{1/p}\stackrel{{\scriptstyle\textrm{Lem~{}\ref{lem:LpVsLq}}}}{{\leq}}n^{1/2-1/p}\cdot\Big{(}\frac{1}{n}\sum_{i=1}^{m}\|\bm{A}_{i}\|_{p}^{p}\Big{)}^{1/p}=n^{1/2-1/p}\Big{(}\frac{1}{n}\sum_{j=1}^{n}\|\bm{A}^{j}\|_{p}^{p}\Big{)}^{1/p}\leq
n^{1/2-1/p}\quad(***)$

Then we use this to estimate that

$\displaystyle\sum_{i=1}^{m}\exp\Big{(}-C_{1}\frac{\Delta^{2}}{\|\bm{A}_{i}\|_{2}^{2}}\Big{)}$
$\displaystyle\leq$
$\displaystyle\sum_{i=1}^{m}p^{p/2}\frac{C_{1}^{p/2}\|\bm{A}_{i}\|_{2}^{p}}{\Delta^{p}}\leq
n\cdot\Big{(}\frac{\sqrt{C_{1}p}n^{1/2-1/p}}{\Delta}\Big{)}^{p}\leq C_{2}n$

if we set $\Delta:=\frac{\sqrt{C_{1}}}{C_{2}^{1/p}}\sqrt{p}\cdot n^{1/2-1/p}$.
Here we have used the following estimate:
Claim I. _For $p\geq 1$ and $y>0$ one has $\exp(-\frac{1}{y})\leq
p^{p/2}y^{p/2}$._
Indeed, for $y>1$, one has $\exp(-\frac{1}{y})<1<p^{p/2}y^{p/2}$. Since
$\exp(\frac{1}{y})=\sum_{k\in\mathbb{N}}\frac{1}{k!\cdot
y^{k}}\geq\frac{1}{k!\cdot y^{k}}$ for any $k\in\mathbb{N}$, one has for
$y\leq 1$:

$\exp\Big{(}-\frac{1}{y}\Big{)}\leq\lceil p/2\rceil!\cdot y^{\lceil
p/2\rceil}\leq\lceil p/2\rceil^{\lfloor p/2\rfloor}y^{p/2}\leq
p^{p/2}y^{p/2}.\qed$

###  4.3 Balancing from $B_{p}^{m}$ to $B_{q}^{m}$

Now we show how to find partial colorings for balancing vectors in the
$B_{p}^{m}$-ball into scalars of the $B_{q}^{m}$-ball using the Lovett-Meka
distribution:

######  Theorem 16.

Let $2\leq p\leq q\leq\infty$, $\bm{x}_{0}\in[-1,1]^{n}$ and let
$\bm{A}\in\mathbb{R}^{m\times n}$ with $\bm{A}^{1},\ldots,\bm{A}^{n}\in
B_{p}^{m}$. Then

$\mathop{\mathbb{E}}_{\bm{x}\sim\pazocal{D}(\bm{A},\bm{x}_{0})}\big{[}\|\bm{A}(\bm{x}-\bm{x}_{0})\|_{q}\big{]}\lesssim\sqrt{\min\big{\\{}p,\log(\tfrac{2m}{n})\big{\\}}}\cdot
n^{1/2-1/p+1/q}$

###### Proof.

We will make use of the inequality
$\|\bm{z}\|_{q}\leq(\|\bm{z}\|_{p}^{p}\cdot\|\bm{z}\|_{\infty}^{q-p})^{1/q}$
for all $\bm{z}\in\mathbb{R}^{m}$, see Lemma 9. Then combining the estimates
from Lemma 14 and Lemma 15 we obtain

$\displaystyle\mathop{\mathbb{E}}_{\bm{x}\sim\pazocal{D}(\bm{A},\bm{x}_{0})}[\|\bm{A}(\bm{x}-\bm{x}_{0})\|_{q}]$
$\displaystyle\leq$
$\displaystyle\mathop{\mathbb{E}}_{\bm{x}\sim\pazocal{D}(\bm{A},\bm{x}_{0})}\big{[}\big{(}\|\bm{A}(\bm{x}-\bm{x}_{0})\|_{p}^{p}\cdot\|\bm{A}(\bm{x}-\bm{x}_{0})\|_{\infty}^{q-p}\big{)}^{1/q}\big{]}\quad\quad(****)$
$\displaystyle\stackrel{{\scriptstyle\textrm{Lem~{}\ref{lem:LM-
UpperBoundOnInfinityNormInTermsOfn}}}}{{\lesssim}}$
$\displaystyle\mathop{\mathbb{E}}_{\bm{x}\sim\pazocal{D}(\bm{A},\bm{x}_{0})}\big{[}\|\bm{A}(\bm{x}-\bm{x}_{0})\|_{p}^{p/q}\big{]}\cdot(\sqrt{p}n^{1/2-1/p})^{(q-p)/q}$
$\displaystyle\stackrel{{\scriptstyle\textrm{Jensen}}}{{\leq}}$
$\displaystyle\mathop{\mathbb{E}}_{\bm{x}\sim\pazocal{D}(\bm{A},\bm{x}_{0})}\big{[}\|\bm{A}(\bm{x}-\bm{x}_{0})\|_{p}\big{]}^{p/q}\cdot(\sqrt{p}n^{1/2-1/p})^{(q-p)/q}$
$\displaystyle\stackrel{{\scriptstyle\textrm{Lem~{}\ref{lem:LM-
ExpectedLpNorm}}}}{{\lesssim}}$
$\displaystyle(\sqrt{pn})^{p/q}\cdot(\sqrt{p}n^{1/2-1/p})^{(q-p)/q}=\sqrt{pn}\cdot
n^{-1/p+1/q}$

Here we have used Jensen’s inequality (see Lemma 7) with the concavity of the
function $y\mapsto y^{p/q}$ for $0<y<\infty$.

Note that this settles the claim in the parameter range
$p\leq\ln(e^{2}\frac{m}{n})$. Now consider the case of
$p>\ln(e^{2}\frac{m}{n})$. We define $p_{0}:=\ln(e^{2}\frac{m}{n})$. Note that
$2\leq p_{0}\leq p$. Then applying the bound of $(****)$ proven above, with
parameters $2\leq p_{0}\leq q$ we obtain

$\displaystyle\Pr_{\bm{x}\sim\pazocal{D}(\bm{A},\bm{x}_{0})}\big{[}\|\bm{A}(\bm{x}-\bm{x}_{0})\|_{q}\big{]}$
$\displaystyle\lesssim$ $\displaystyle\sqrt{p_{0}}\cdot
n^{1/2-1/p_{0}+1/q}\cdot\max\\{\|\bm{A}^{j}\|_{p_{0}}:j=1\ldots,n\\}$
$\displaystyle\leq$ $\displaystyle\sqrt{p_{0}}\cdot n^{1/2-1/p+1/q}\cdot
m^{1/p_{0}-1/p}\cdot\max\\{\underbrace{\|\bm{A}^{j}\|_{p}}_{\leq
1}:j=1,\ldots,n\\}$ $\displaystyle=$ $\displaystyle\sqrt{p_{0}}\cdot
n^{1/2-1/p+1/q}\cdot\underbrace{\Big{(}\frac{m}{n}\Big{)}^{-1/p}}_{\leq
1}\cdot\Big{(}\frac{m}{n}\Big{)}^{1/p_{0}}$ $\displaystyle\leq$
$\displaystyle\sqrt{\ln\Big{(}e^{2}\frac{m}{n}\Big{)}}\cdot
n^{1/2-1/p+1/q}\cdot\underbrace{\Big{(}\frac{m}{n}\Big{)}^{1/\ln(e^{2}\frac{m}{n})}}_{\leq
O(1)}$

This completes the proof. ∎

###  4.4 From partial colorings to full colorings

The result from Theorem 16 allows us to find a partial coloring — the next
step is to iterate the argument in order to find a full coloring:

###### Proof of Theorem 3.

Consider $n$ vectors from $B_{p}^{m}$ that we conveniently write as column
vectors $\bm{A}^{1},\ldots,\bm{A}^{n}\in B_{p}^{m}$. We set
$\bm{x}_{0}:=\bm{0}\in\mathbb{R}^{n}$ and $n_{0}:=n$. In iteration
$t=0,1,\ldots$ we have maintained a vector $\bm{x}_{t}\in[-1,1]^{n}$ where
$n_{t}:=|\\{i\in[n]\mid-1<x_{t}(i)<1\\}|$ denotes the number of uncolored
elements. We draw $\bm{x}_{t+1}\sim\pazocal{D}(\bm{A},\bm{x}_{t})$ and repeat
until the bound of the expectation provided by Theorem 16 is attained (say up
to a factor of 2). In particular

$\big{\|}\bm{A}(\bm{x}_{t+1}-\bm{x}_{t})\big{\|}_{q}\lesssim\sqrt{\min\big{\\{}p,\log\big{(}\tfrac{2m}{n_{t}}\big{)}\big{\\}}}\cdot
n_{t}^{1/2-1/p+1/q}$

and $n_{t+1}\leq n_{t}/2$. Then $n_{t+1}\leq\frac{n}{2^{t}}$ and so
$\bm{x}^{*}:=\bm{x}_{\log_{2}(n)+1}$ will be in $\\{-1,1\\}^{n}$ and by the
triangle inequality, the discrepancy is at most

$\|\bm{A}\bm{x}^{*}\|_{q}\lesssim\sum_{t\geq
0}\sqrt{\min\big{\\{}p,\log\big{(}\tfrac{2m}{n/2^{t}}\big{)}\big{\\}}}\cdot(n/2^{t})^{1/2-1/p+1/q}\lesssim\frac{\sqrt{\min\\{p,\log(\frac{2m}{n})\\}}}{1/2-1/p+1/q}n^{1/2-1/p+1/q}$

To see the ultimate inequality, consider the exponent $\alpha:=1/2-1/p+1/q>0$.
Then it takes $1/\alpha$ iterations until the quantity $n_{t}^{\alpha}$ has
decreased by a factor of 2 (while the term $\log(2m/n_{t})$ has a miniscule
growth). Then the cumulated discrepancy is dominated by the first
$\frac{1}{\alpha}$ terms. The running time is bounded by $O(\log n)\cdot
T(m,n)$. ∎

##  5 Approximate Carathéodory bounds for $\|\cdot\|_{p}$ norms

Next, we prove the bound on $\textrm{ac}_{k}(B_{p}^{m},B_{q}^{m})$ claimed in
Theorem 4:

###### Proof of Theorem 4.

Let $2\leq p\leq q\leq\infty$. We apply the reduction to the vector balancing
constant from Theorem 2 and combine this with the bound from Theorem 3:

$\displaystyle\textrm{ac}_{k}(B_{p}^{m},B_{q}^{m})$
$\displaystyle\stackrel{{\scriptstyle\textrm{Thm~{}\ref{thm:ReductionApxCaraToVB}}}}{{\leq}}$
$\displaystyle\sum_{\ell\geq
1}\frac{1}{k2^{\ell}}\cdot\textrm{vb}_{k2^{\ell}}(B^{m}_{p},B^{m}_{q})$
$\displaystyle\stackrel{{\scriptstyle\textrm{Thm~{}\ref{thm:VectorBalancingFromBpToBq}}}}{{\lesssim}}$
$\displaystyle\frac{1}{\frac{1}{2}-\frac{1}{p}+\frac{1}{q}}\sum_{\ell\geq
1}\frac{\sqrt{\min\\{p,\log(\frac{2m}{k2^{\ell}})\\}}}{(k2^{\ell})^{1/2+1/p-1/q}}$
$\displaystyle\lesssim$
$\displaystyle\frac{1}{\frac{1}{2}-\frac{1}{p}+\frac{1}{q}}\cdot\frac{\sqrt{\min\\{p,\log(\frac{2m}{k})\\}}}{k^{1/2+1/p-1/q}}.$

Note that the exponent $\alpha:=1/2+1/p-1/q$ satisfies $\alpha\geq 1/2$ and so
the sum is already dominated by the very first term. The running time to find
the vectors $\bm{v}_{1},\ldots,\bm{v}_{k}$ is dominated by $O(\log m)$ calls
to find the coloring behind $\textrm{vb}_{t}(B_{p}^{m},B_{q}^{m})$ where
$t\leq m+1$ which results in a total running time of $O(\log^{2}m)\cdot
T(m,m+1)\leq O(m^{1+\omega}\log^{2}(m))$ as $\omega\geq 2$. ∎

######  Remark 1.

In the case where $p=2$ and $q=\infty$, we can apply Theorem 4 with
$q^{\prime}:=\log_{2}m$ to obtain
$\textrm{ac}_{k}(B_{2}^{m},B_{\infty}^{m})\lesssim\frac{\log m}{k}$ by noting
that Lemma 8 implies $\|\bm{x}\|_{\infty}\leq\|\bm{x}\|_{\log_{2}m}\leq
2\|\bm{x}\|_{\infty}$ for any $\bm{x}\in\mathbb{R}^{m}$. But for $P=B^{m}_{2}$
and $Q=B^{m}_{\infty}$ one has
$\textrm{vb}_{k}(B^{m}_{2},B^{m}_{\infty})\lesssim\sqrt{\log m}$ by the result
of Banaszczyk [Ban98], so that Theorem 2 yields the improved bound

$\textrm{ac}_{k}(B_{2}^{m},B_{\infty}^{m})\lesssim\frac{\sqrt{\log m}}{k}.$

It remains an interesting open question whether this may be improved to
$O(\frac{1}{k})$.

##  6 Lower bounds for vector balancing

In this section we show that the vector balancing bounds in Theorem 3 are
tight up to the factor of $\frac{1}{2}-\frac{1}{p}+\frac{1}{q}$:

###### Proof of Theorem 6.

First, let us focus on the case when $m\leq 2^{p}n$ so that
$\log(2m/n)=\min\Big{\\{}p,\log\Big{(}\frac{2m}{n}\Big{)}\Big{\\}}$. We will
also assume that $m\geq 8n$, since otherwise we can use instead
$n^{\prime}:=\lfloor n/8\rfloor$ and add $n-n^{\prime}$ columns of zeros. Let
$\bm{B}$ denote an $m\times n$ random matrix with i.i.d $\pm 1$ entries. For
any fixed $\bm{x}\in\\{-1,1\\}^{n}$, let $N_{\bm{x}}$ denote the number of
rows $i\in[m]$ with $\langle{\bm{B}_{i}},{\bm{x}}\rangle\geq\lambda\sqrt{n}$
for $\lambda:=\sqrt{\frac{2}{9}\log\Big{(}\frac{m}{2n}\Big{)}}$. Since
$\lambda\leq\sqrt{n}/2$, by Lemma 11 we have

$\Pr\Big{[}\langle{\bm{B}_{i}},{\bm{x}}\rangle\geq\lambda\sqrt{n}\Big{]}\geq\frac{2n}{m},$

so that $\mathop{\mathbb{E}}[N_{\bm{x}}]\geq 2n$. The standard Chernoff bound
then gives $\Pr[N_{\bm{x}}\leq(1-0.9)\cdot 2n]<2^{-n}$, so that by the union
bound there exists a matrix $\bm{B}\in\\{-1,1\\}^{m\times n}$ for which
$N_{\bm{x}}\geq n/5$ for all $\bm{x}\in\\{-1,1\\}^{n}$. Thus for any such
$\bm{x}$,

$\|\bm{Bx}\|_{q}\geq(|N_{\bm{x}}|\cdot(\lambda\sqrt{n})^{q})^{1/q}\gtrsim
n^{1/2+1/q}\log\Big{(}\frac{m}{2n}\Big{)}^{1/2}\gtrsim
n^{1/2+1/q}\log\Big{(}\frac{2m}{n}\Big{)}^{1/2},$

where in the last step we used $m\geq 8n$. The matrix $\bm{A}:=m^{-1/p}\bm{B}$
has columns in $B^{m}_{p}$ and

$\|\bm{Ax}\|_{q}\gtrsim\sqrt{\log\Big{(}\frac{m}{2n}\Big{)}}\cdot\frac{n^{1/2+1/q}}{m^{1/p}}\gtrsim\sqrt{\log\Big{(}\frac{m}{2n}\Big{)}}\cdot
n^{1/2-1/p+1/q}$

for all $\bm{x}\in\\{-1,1\\}^{n}$, as claimed.

For the case when $m\geq 2^{p}n$ we may use the same construction for
$m^{\prime}:=\lfloor 2^{p}n\rfloor$ with $m-m^{\prime}$ additional rows of
zeros. ∎

## References

  * [Ban98] W. Banaszczyk.  Balancing vectors and Gaussian measures of $n$-dimensional convex bodies.  Random Structures Algorithms, 12(4):351–360, 1998.
  * [Ban10] N. Bansal.  Constructive algorithms for discrepancy minimization.  In FOCS, pages 3–10, 2010.
  * [Bar15] S. Barman.  Approximating Nash equilibria and dense bipartite subgraphs via an approximate version of Caratheodory’s theorem.  In Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’15, pages 361–369, New York, NY, USA, 2015. Association for Computing Machinery.
  * [BF81] J. Beck and T. Fiala.  “Integer-making” theorems.  Discrete Appl. Math., 3(1):1–8, 1981.
  * [BN13] J. Bourgain and J. Nelson.  Toward a unified theory of sparse dimensionality reduction in euclidean space.  CoRR, abs/1311.2542, 2013.
  * [BSV20] V. Bhargava, S. Saraf, and I. Volkovich.  Deterministic factorization of sparse polynomials with bounded individual degree.  J. ACM, 67(2), may 2020.
  * [CP21] C. W. Combettes and S. Pokutta.  Revisiting the approximate Carathéodory problem via the Frank-Wolfe algorithm.  Mathematical Programming, 2021.
  * [DFMS22] A. Deligkas, J. Fearnley, T. Melissourgos, and P. G. Spirakis.  Approximating the existential theory of the reals.  Journal of Computer and System Sciences, 125:106–128, 2022.
  * [DNTT18] D. Dadush, A. Nikolov, K. Talwar, and N. Tomczak-Jaegermann.  Balancing vectors in any norm.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 1–10, 2018.
  * [KY15] P. Klein and N. E. Young.  On the number of iterations for Dantzig–Wolfe optimization and packing-covering approximation algorithms.  SIAM Journal on Computing, 44(4):1154–1172, 2015.
  * [LM12] S. Lovett and R. Meka.  Constructive discrepancy minimization by walking on the edges.  In FOCS, pages 61–67, 2012.
  * [LSV86] L. Lovász, J. Spencer, and K. Vesztergombi.  Discrepancy of set-systems and matrices.  European Journal of Combinatorics, 7(2):151–160, 1986.
  * [MLVW17] V. S. Mirrokni, R. Paes Leme, A. Vladu, and S. C. Wong.  Tight bounds for approximate Carathéodory and beyond.  In D. Precup and Y. W. Teh, editors, Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 2440–2448. PMLR, 2017.
  * [Pis81] G. Pisier.  Remarques sur un résultat non publié de B. Maurey.  Séminaire d’Analyse fonctionnelle (dit "Maurey-Schwartz"), 1980-1981.  talk:5.
  * [RR20] V. Reis and T. Rothvoss.  Vector balancing in Lebesgue spaces.  CoRR, abs/2007.05634, 2020.
  * [Spe85] J. Spencer.  Six standard deviations suffice.  Trans. Amer. Math. Soc., 289(2):679–706, 1985.
  * [Ver18] R. Vershynin.  High-Dimensional Probability: An Introduction with Applications in Data Science.  Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.

##  Appendix A The Lovett-Meka random walk

In this section we want to justify Theorem 1. First, the original main
technical statement of Lovett and Meka [LM12] is as follows:

######  Theorem 17 ([LM12]).

Let $\bm{A}_{1},\ldots,\bm{A}_{m}\in\mathbb{R}^{n}$,
$\bm{x}_{0}\in[-1,1]^{n}$, $\delta>0$ small enough and let
$\lambda_{1},\ldots,\lambda_{m}\geq 0$ so that
$\sum_{i=1}^{m}\exp(-\lambda_{i}^{2}/16)\leq\frac{n}{16}$. Then there exists
an efficient randomized algorithm which with probability at least
$\frac{1}{10}$ finds a point $\bm{x}\in[-1,1]^{n}$ so that

  1. (i)

$|\left<\bm{A}_{i},\bm{x}-\bm{x}_{0}\right>|\leq\lambda_{i}\|\bm{A}_{i}\|_{2}$
for all $i=1,\ldots,m$.

  2. (ii)

$|x_{j}|\geq 1-\delta$ for at least $n/2$ many indices.

Moreover, the algorithm runs in time
$O((m+n)^{3}\cdot\delta^{-2}\log(mn/\delta))$.

First, note that if $\Delta$ is a parameter with
$\sum_{i=1}^{m}\exp(-\frac{\Delta^{2}}{16\|\bm{A}_{i}\|_{2}^{2}})\leq\frac{n}{16}$,
then $\lambda_{i}:=\frac{\Delta}{\|\bm{A}_{i}\|_{2}}$ is a feasible choice.
The algorithm behind Theorem 17 works as follows: let $\gamma>0$ be a
parameter that is logarithmically smaller than $\delta$. We compute a random
sequence $\bm{x}_{0},\bm{x}_{1},\bm{x}_{2},\ldots$ of points. In iteration $t$
we have already computed $\bm{x}_{t}$; next we define a subspace
$V_{t}\subseteq\mathbb{R}^{n}$ that is orthogonal to coordinates $\bm{e}_{i}$
with $|x_{i}|\geq 1-\delta$ and to directions $\bm{A}_{i}$ with
$|\left<\bm{A}_{i},\bm{x}-\bm{x}_{0}\right>|\geq\lambda_{i}-\delta$. Then
update $\bm{x}_{t+1}=\bm{x}_{t}+\gamma\bm{u}_{t}$ where $\bm{u}_{t}\sim
N(\bm{0},\bm{I}_{V_{t}})$ is a random Gaussian from that subspace $V_{t}$.

What is slightly unsatisfactory is that we will not actually have coordinates
equal to $\pm 1$. But there is an easy way to remedy this: consider the
polyhedron
$K:=\\{\bm{x}\in[-1,1]^{n}\mid|\left<\bm{A}_{i},\bm{x}-\bm{x}_{0}\right>|\leq\lambda_{i}\|\bm{A}_{i}\|_{2}\;\;\forall
i=1,\ldots,m\\}$. We say that a coordinate $j$ is _tight_ for a point $\bm{x}$
if $|x_{j}|=1$ and a constraint $i$ is _tight_ for $\bm{x}$ if
$|\left<\bm{A}_{i},\bm{x}-\bm{x}_{0}\right>|=\lambda_{i}\|\bm{A}_{i}\|_{2}$.
Then consider the following random walk:

  1. (1)

FOR $t=1,2,\ldots,8n$ DO

    1. (2)

Let
$V_{t}:=\\{\bm{y}\in\mathbb{R}^{n}\mid\left<\bm{y},\bm{x}_{t}\right>=0;\;y_{j}=0\textrm{
if }j\in[n]\textrm{ is tight for
}\bm{x}_{t};\;\left<\bm{A}_{i},\bm{y}\right>=0\textrm{ if }i\textrm{ is tight
for }\bm{x}_{t}\\}$. If $\dim(V_{t})\leq\frac{n}{8}$ then return FAIL

    2. (3)

Let $\bm{u}_{t}\sim S^{n-1}\cap V_{t}$.

    3. (4)

Let $r_{t}:=\max\\{r\geq 0\mid\bm{x}_{t}+r\bm{u}_{t}\in K\textrm{ and
}\bm{x}_{t}-r\bm{u}_{t}\in K\\}$

    4. (5)

Let $\delta_{t}:=\min\\{1,r_{t}\\}$

    5. (6)

Update $\bm{x}_{t+1}:=\bm{x}_{t}+\sigma_{t}\delta_{t}\bm{u}_{t}$ where
$\sigma_{t}\sim\\{-1,1\\}$

    6. (7)

IF $\bm{x}_{t+1}$ has at least $n/2$ coordinates tight THEN return
$\bm{x}_{t+1}$.

  2. (8)

RETURN FAIL

The key modification compared to [LM12] is that the step length is not uniform
but it is capped so that we do not exit $K$. As we walk orthogonal to the
current point, one has
$\|\bm{x}_{t+1}\|_{2}^{2}=\|\bm{x}_{t}\|_{2}^{2}+\delta_{t}^{2}$ for all $t$
and so $\sum_{t}\delta_{t}^{2}\leq 4n$. Let us call a step $t$ _long_ if
$\delta_{t}=1$ and _short_ otherwise. So we cannot have more than $4n$ many
long steps. But in each short step (i.e. $\delta_{r}=r_{t}$) we have a
probability of at least 1/2 that some coordinate or constraint becomes tight
and this cannot happen more than $\frac{7}{8}n$ times before exiting at (2).
So the probability of reaching $(8)$ is less than $(1/2)^{n}$.

Now let $\bm{x}$ be the random vector when the algorithm stops (either in (2),
(7) or (8)). Fix a constraint $i$; the next step is to analyze the
concentration behaviour of $\left<\bm{A}_{i},\bm{x}-\bm{x}_{0}\right>$. In
each iteration $t$ one has
$\|\left<\bm{A}_{i},\sigma_{t}\delta_{t}\bm{u}_{t}\right>\|_{\psi_{2}}\leq\|\left<\bm{A}_{i},\bm{u}_{t}\right>\|_{\psi_{2}}\lesssim\frac{\|\bm{A}_{i}\|_{2}}{\sqrt{n}}$
by Lemma 10 as $\bm{u}_{t}$ is a unit vector from a subspace of dimension at
least $n/8$. As there are at most $8n$ iterations, we have
$\|\left<\bm{A}_{i},\bm{x}-\bm{x}_{0}\right>\|_{\psi_{2}}\lesssim
8n\cdot(\frac{\|\bm{A}_{i}\|_{2}}{\sqrt{n}})^{2}\lesssim\|\bm{A}_{i}\|_{2}$.
Then
$\Pr[|\left<\bm{A}_{i},\bm{x}_{0}-\bm{x}\right>|\geq\lambda_{i}\|\bm{A}_{i}\|_{2}]\leq\exp(-C_{1}\lambda_{i}^{2})$
by Lemma 10.(D) for some constant $C_{1}>0$. In other words, the probability
that the $i$th constraint becomes tight at any point in the algorithm is upper
bounded by $\exp(-C_{1}\lambda_{i}^{2})$ and so with good probability the
number of tight constraints remains below, say, $\frac{n}{4}$. This gives an
upper bound on the probability to exit in (2). Finally, we define
$\pazocal{D}(\bm{A},\bm{x}_{0})$ as the vector $\bm{x}_{t+1}$ returned in (7),
that means conditioned on the run being successful.

We briefly discuss the running time. In every of the at most $8n$ iterations
we compute a basis of $V_{t}$ which using fast matrix multiplication can be
done in time $O(n^{\omega})$. Then to compute $r_{t}$ (and to determine which
constraints determine $V_{t}$) can be done in time $O(nm)$. This results in
the claimed bound of $T(m,n)\leq O(n^{1+\omega}+n^{2}m)$.