\section{Introduction}

\subsection{Background}

In the April 1986 issue of \emph{The American Mathematical Monthly}, Richard Guy~\cite{Guy86} presented an open question, attributed to Boguslav Tomaszewski:
\begin{question}
Consider $n$ real numbers $a_1,a_2,\ldots,a_n$ such that $\sum_i a_i^2=1$. Of the $2^n$ expressions $|\epsilon_1 a_1 + \ldots + \epsilon_n a_n|$, with $\epsilon_i=\pm 1$, $1 \leq i \leq n$, can there be more with value $>1$ than with value $\leq 1$?
\end{question}
In the first paper studying the problem, Holzman and Kleitman~\cite{HK92} presented several equivalent formulations:
\begin{itemize}
\item \emph{Sum partitions:} Let $a_1,\ldots,a_n$ be real numbers with $\sum_i a_i^2=1$. Is it true that in at least half of the partitions of $\sum a_i$ into two sums, the sums differ by at most $1$?

\item \emph{Chebyshev-type inequality:} Let $X=\sum_i a_i x_i$, where $\{x_i\}$ are uniformly distributed in $\{-1,1\}$ and independent. Is it true that $\Pr[|X| \leq \sqrt{\var(X)}] \geq 1/2$? Note that Chebyshev's inequality yields a lower bound of $0$ for this probability.

\item \emph{A ball and a cube:} Consider an $n$-dimensional ball and a smallest $n$-dimensional cube containing it. Is it true that for any pair of parallel supporting hyperplanes of the ball, at least half the vertices of the cube lie between (or on) the two hyperplanes?
\end{itemize}
In the sequel, we use the probabilistic notation $X=\sum a_i x_i$, normalizing such that $\sum a_i^2=1$. Holzman and Kleitman~\cite{HK92} proved the lower bound $\Pr[|X|<1] \geq 3/8$, which is tight for $X=\frac{1}{2}(x_1+x_2+x_3+x_4)$, and were not able to prove a stronger lower bound for $\Pr[|X| \leq 1]$. They conjectured that $\Pr[|X|\leq 1] \geq 1/2$, which would be tight, e.g., for $X=a_1 x_1+a_2 x_2$ with any $|a_1|,|a_2|<1$. This conjecture became known as \emph{Tomaszewski's conjecture} or \emph{Tomaszewski's problem}.

As is suggested by its equivalent formulations, Tomaszewski's problem and its variants naturally appear in diverse fields, including probability theory~\cite{BD15,Pinelis12}, geometric analysis~\cite{KR20}, optimization and operation research~\cite{BNR02,So09}, statistics~\cite{Pinelis94}, and theoretical computer science~\cite{DDS16,DG20,Tan12}. It became well-known, and was mentioned in lists of open problems in various fields (e.g.,~\cite{F+14,Hiriart09}).

A number of works obtained partial results toward Tomaszewski's conjecture. Ben-Tal et al.~\cite{BNR02} (who were not aware of the previous work on the conjecture and arrived to it independently, from applications to optimization) proved that $\Pr[|X|\leq 1] \geq 1/3$. Shnurnikov~\cite{Shnurnikov12} improved their lower bound to $0.36$. Boppana and Holzman~\cite{BH17} were the first to cross the $3/8$ barrier, proving a lower bound of $0.406$, and Boppana et al.~\cite{BHZ20} further improved the lower bound to $0.428$. Very recently, Dvo{\v{r}}{\'{a}}k et al.~\cite{DHT20} proved a lower bound of $0.46$, which is the best currently known bound.

Several other authors proved the conjecture in special cases: Bentkus and Dzinzalieta~\cite{BD15} proved it in the case $\max |a_i| \leq 0.16$, Hendriks and van Zuijlen~\cite{HZ17a} proved it for $n \leq 9$ (a proof-sketch in that case, using different methods, was presented earlier by von Heymann~\cite{Heymann12}), van Zuijlen~\cite{vanZuijlen11} proved it when all $a_i$'s are equal, and Toufar~\cite{Toufar18} extended his result to the case where all $a_i$'s but one are equal. In another direction, De et al.~\cite{DDS16} presented an algorithm that allows approximating $\min \{\Pr[|X|\leq 1]|X=\sum a_i x_i\}$ up to an additive error of $\epsilon$. Unfortunately, the complexity of the algorithm is $\exp(O(1/\epsilon^6))$.

\subsection{Our results}

In this paper we prove Tomaszewski's conjecture.
\begin{theorem}\label{thm:main}
Let $X=\sum_{i=1}^n a_i x_i$, where $\sum_{i=1}^{n} a_i^2=1$ and $\{x_i\}$ are independent and uniformly distributed in $\{-1,1\}$. Then
\begin{equation}\label{eq:main}
\Pr[|X|\leq 1] \geq 1/2.
\end{equation}
\end{theorem}
Our result may be interpreted within the general context of \emph{tail bounds for Rademacher sums}. A Rademacher sum is a random variable $X=\sum a_i x_i$, where the $x_i$'s are i.i.d. Rademacher random variables (i.e., are uniformly distributed in $\{-1,1\}$). Estimates on Rademacher sums were studied in numerous papers, both for their own sake (e.g.,~\cite{BGH01,Veraar08}) and for the sake of applications to statistics~\cite{Efron69} and to optimization~\cite{BNR02}. A main direction in this study is obtaining upper and lower bounds on the tail probability $\Pr[|X| > t]$, aiming at showing that the tail of any such $X$ behaves `similarly' to the tail of a Gaussian random variable with the same variance
(see, e.g.,~\cite{BD15,Eaton70,Pinelis12} for upper bounds and~\cite{HK94,MS90,Oles96} for lower bounds).

One of the upper bounds on the tail, proved by Dzindzalieta~\cite{Dzindzalieta14a}, asserts that
\[
\Pr[X>t] \leq \frac{1}{4} + \frac{1}{8}(1-\sqrt{2-\frac{2}{t^2}}), \qquad \forall 1<t \leq \sqrt{2}.
\]
when $\var(X)=1$.
Theorem~\ref{thm:main} improves over this result, showing that
\begin{equation}
\Pr[X>t] \leq 1/4, \qquad \forall t \geq 1,
\end{equation}
which is tight for all $t<\sqrt{2}$, due to $X=\frac{1}{\sqrt{2}}x_1+\frac{1}{\sqrt{2}}x_2$.

\medskip Furthermore, as was observed by Dzindzalieta~\cite{Dzindzalieta14a}, Theorem~\ref{thm:main} implies the more general:
\begin{equation}\label{eq:dzin-intro1}
\Pr[|X|<t] \geq \Pr[|X|>1/t], \qquad \forall t>0,
\end{equation}
and notably, an improvement of~\eqref{eq:main},
$
	\Pr[|X| < 1] + \frac{1}{2}\Pr[|X|=1] \geq \frac{1}{2},
$
being tight for $X= 1\cdot x_1$.



\subsection{Our tools}

The proof of Theorem~\ref{thm:main} uses four main tools.

\paragraph{A new local concentration inequality for Rademacher sums.} In~\cite{KK17}, the authors introduced several local concentration inequalities that allow comparing the probabilities $\Pr[X \in I]$ and $\Pr[X \in J]$, for segments (or rays) $I,J$. We enhance some techniques of~\cite{KK17} and prove:
\begin{theorem}[segment comparison]\label{thm:seg_compare_intro}
		Let $X = \sum_{i=1}^{n} a_{i} x_{i}$ be a Rademacher sum, and write $M=\max_i |a_i|$. For any $A, B, C, D \in \mathbb{R}$ with $|A| \leq \min(B,C)$, $2M \leq C-A$ and $D-C + \min(2M, D-B) \leq B-A$, we have
		\begin{equation}
			\Pr[X \in (C,D)] \leq \Pr[X \in (A,B)].
		\end{equation}
   
\end{theorem}
We prove Theorem~\ref{thm:seg_compare_intro} by constructing an explicit injection.

\paragraph{An improved Berry-Esseen inequality for Rademacher sums.} The classical Berry-Esseen theorem~(\cite{Berry41,Esseen42}) allows approximating a sum of independent random variables by a Gaussian. If $X=\sum a_i x_i$ where all $a_i$'s are `sufficiently small', this allows deducing~\eqref{eq:main}, since for a Gaussian $Z\sim N(0,1)$ we have $\Pr[|Z|\leq 1] \approx 0.68$. Specifically, as was observed by Bentkus and Dzindzalieta~\cite{BD15}, Tomaszewski's conjecture in the case $\max |a_i| \leq 0.16$ follows from the Berry-Esseen bound.

We show that for Rademacher sums, improved Berry-Esseen type bounds (i.e., a tighter approximation by a Gaussian) can be obtained. 
We prove these new bounds via a method proposed by Prawitz~\cite{pra72} which employs the characteristic functions of $X$ and of a Gaussian to bound the difference between the distributions. Our key observation here is that in the case of Rademacher sums, Prawitz' method can be refined, yielding significantly stronger bounds. Then, we use these bounds to deduce Theorem~\ref{thm:main} in the range $\max |a_i| \leq 0.31$ (compared to $0.16$ of~\cite{BD15}) and in cases where the second-largest or the third-largest among the $a_i$'s is `sufficiently small'. We conjecture that these bounds can be improved further; see Section~\ref{sec:open}.

\paragraph{A `semi-inductive' approach, using a stopping time argument.} In their proof of the lower bound $\Pr[|X|\leq 1] \geq 1/3$, Ben-Tal et al.\cite{BNR02} introduced a `stopping time' argument, which treats $X$ as a sum $X=X'+X''$ where $X'=\sum_{i=1}^k a_i x_i$ and $X''=\sum_{i=k+1}^n a_i x_i$, and shows that if the partial sum $X'$ is `a little less than $1$', then the final sum $X$ has a decent chance of remaining less than $1$ in absolute value. Variants of this argument (which was attributed in~\cite{BNR02} to P. Van der Wal) were used in all subsequent proofs of lower bounds for Tomaszewski's problem (i.e.,~\cite{BHZ20,BH17,DHT20,Shnurnikov12}).

In our proof, we also employ a `stopping time' argument, but in a somewhat different manner. We use it to show that the statement of Theorem~\ref{thm:main} regarding $X=\sum_{i=1}^n a_i x_i$, with $a_1+a_2\geq 1$, follows from the assertion of Theorem~\ref{thm:main} for $Z=\sum_{i=1}^{m} b_i x_i$, with properly chosen $m<n$ and $\{b_i\}$. However, as it might be that $b_1+b_2 < 1$, this argument is not really inductive, and is completely useless, unless we can prove~\eqref{eq:main} in the case $a_1+a_2<1$ by different tools.

The semi-inductive approach is used once again, when treating the case $a_1 \in [0.31,0.387] \wedge a_1+a_2+a_3 \geq 1$ of Theorem~\ref{thm:main}.

\paragraph{A refinement of Chebyshev's inequality.} We make repeated use of the following, rather standard, refinement of Chebyshev's inequality:

\begin{proposition}\label{prop:Intro-Chebyshev}
Let $X$ be a symmetric (around $0$) random variable with $\var(X) = 1$, and let $c_0,\ldots,c_n,d_1,\ldots,d_m \in \mathbb{R}$ be such that
		\[
		0 = c_0 \leq c_1 \leq \ldots \leq c_n = 1 = d_0 \leq d_1 \leq \ldots \leq d_m.
		\]
Then
        \begin{equation}
		\sum_{i=0}^{n-1} (1-c_i^2) \Pr[X \in (c_i, c_{i+1}]] \geq \sum_{i=1}^{m} (d_i^2-d_{i-1}^2) \Pr[X \geq d_i].
		\end{equation}
\end{proposition}

\paragraph{Proof outline.} In the proof of Theorem~\ref{thm:main}, we consider several cases, according to the sizes of the $a_i$'s, and prove the assertion in each of them separately using the tools described above. In particular, the case $a_1+a_2 \geq 1$ is covered by the aforementioned semi-inductive argument, the case $\max |a_i| \leq 0.31$ is proved by the refined Berry-Esseen inequality, and the cases `in the middle' are proved via various combinations of the segment comparison argument and the refined Chebyshev inequality, sometimes using also the refined Berry-Esseen bound.

Unfortunately, this part of the proof requires somewhat grueling computations, including two cases in which a light computer-aided check is applied. For the sake of readability, we divide the proofs into their `essential' part and their `calculation' part, and relay the calculations to the appendices.

\paragraph{Organization of the paper.}
In Section~\ref{sec:preliminaries} we introduce notation, a basic lemma, and a more detailed outline of the proof. The segment comparison argument (i.e., Theorem~\ref{thm:seg_compare_intro}) is presented in Section~\ref{sec:comparison}. In Section~\ref{sec:BE} we present the refined Berry-Esseen bounds. The semi-inductive argument for the case $a_1+a_2\geq 1$ is given in Section~\ref{sec:induction}. The rest of the cases are presented in Sections~\ref{sec:055}--\ref{sec:remaining} and Appendices~\ref{sec:31big}--\ref{sec:0.31<a_1<0.387}. We conclude with several open problems in Section~\ref{sec:open}.

\section{Preliminaries and Structure of the Proof}
\label{sec:preliminaries}

This section presents notation, a basic lemma, and the structure of the proof in more detail.

\subsection{Notation}

\paragraph{Standard notation.} $\phantom{}$


\medskip For $n \in \mathbb{N}$, $[n]$ denotes $\{1,2,\ldots,n\}$.

\medskip For $A,B,C \in \mathbb{R}$, $A+[B,C]$ denotes the segment $[A+C,B+C]$.

\medskip The shorthand $A_1,A_2,\ldots,A_m=x_1,x_2,\ldots,x_m$  denotes the $m$ equalities $A_i=x_i$, $i\in [m]$.

\medskip The shorthands LHS and RHS denote the left hand side and the right hand side of an equation (or an inequality).

\paragraph{Setting.} Throughout the paper, $X$ denotes a normalized Rademacher sum, that is, $X=\sum_{i=1}^n a_i x_i$, where $\sum_{i=1}^{n} a_i^2=1$ and $\{x_i\}$ are independent and uniformly distributed in $\{-1,1\}$. Without loss of generality, we always assume
\[
a_1 \geq a_2 \geq \ldots \geq a_n > 0.
\]
Note that sometimes, we pass from $X$ to an auxiliary random variable, which we denote by $X'=\sum_{i=1}^m b_i x_i$. In such cases, nothing is assumed on the $\{b_i\}$, unless stated otherwise explicitly.

\paragraph{Precision.} The paper contains explicit real numbers, which we present in decimal expansion. When we write these, we mean the exact value we write; we never write a rounded value and mean `a close' number. We make such roundings by writing, e.g.,  $\pi=3.1416 \pm 10^{-5}$.
		
\paragraph{Notation for segments.} We use the somewhat non-standard notation
\begin{equation}\label{eq-def:segment}
\hpr{X}{a}{b} =
\begin{cases}
\Pr[X \in [a,b]] - \Pr[X=a]/2 - \Pr[X=b]/2,		& a<b \\
0,								                & \mrm{Otherwise}
\end{cases}.
\end{equation}
Note that we have
\begin{equation}\label{eq:additivity}
A \leq B \leq C \implies \hpr{X}{A}{C} = \hpr{X}{A}{B} + \hpr{X}{B}{C}.
\end{equation}
Similarly, for $a\leq b$ we denote $\Pr[X \in \langle a,b]] = \Pr[X \in [a,b]]-\Pr[X=a]/2$, and $\Pr[X \in [a,b \rangle]=\Pr[X \in [a,b]] - \Pr[X=b]/2$.

\subsection{A basic lemma -- elimination of variables}

The following lemma allows eliminating several $x_i$'s, by taking into account each possible value of these $x_i$'s separately. The lemma exchanges Tomaszewski's conjecture~\eqref{eq:main} by inequalities which are occasionally easier to approach.
\begin{lemma}\label{lem:nm}
Let $X = \sum_{i=1}^{n} a_i x_i$ be a Rademacher sum with  $\var(X) = 1$ and let $m < n$. Write
\begin{equation}\label{Eq:Elimination1}
\sigma = \sqrt{1-\sum_{i=1}^{m} a_i^2} \qquad \mbox{and} \qquad X' = \sum_{i=m+1}^{n} a_i' x_i, \qquad \mbox{with} \qquad a_i' = \frac{a_i}{\sigma}.
\end{equation}
Tomaszewski's assertion~\eqref{eq:main} is equivalent to
\begin{equation}\label{Eq:Elimination2}
\sum_{j=0}^{2^m-1} \Pr[X' > T_j] \leq 2^{m-2},
\end{equation}
where $\{T_j\} = (1 \pm a_1 \pm \cdots \pm a_m)/\sigma$ ranges over all $2^m$ options.
\end{lemma}
	
\begin{proof}
As $X$ is symmetric,~\eqref{eq:main} is equivalent to $\Pr[X > 1] \leq 1/4$. By the law of total probability,
$
2^{m} \Pr[X > 1] = \sum_{j} \Pr[X' > T_j],
$
implying the lemma.
\end{proof}

Lemma~\ref{lem:nm} is simple yet useful. For example, applying the lemma with $m=1$, one can see that~\eqref{eq:main} is equivalent to the inequality
\begin{equation}\label{eq:nm1}
\Pr[X' \in \li\langle 0, t\right] ] \geq \Pr[X' > 1/t],
\end{equation}
where
\begin{equation}\label{Eq:Prelim-Eliminate-one}
\sigma = \sqrt{1-a_1^2}, \qquad X'=\sum_{i=2}^n \frac{a_i}{\sigma}x_i, \qquad \mbox{and} \qquad t=\sqrt{\frac{1-a_1}{1+a_1}}.
\end{equation}
This readily implies the aforementioned observation of Dzindzalieta~\cite{Dzindzalieta14a} that Tomaszewski's conjecture is equivalent to the more general inequality~\eqref{eq:dzin-intro1}.


\subsection{Hard cases for the proof}\label{ssec:hard-cases}

There are several classes of Rademacher sums which are `hard to handle' with our tools. These classes motivate the partition into cases used in the proof.

One of the obstacles we have to overcome, is the difficulty in distinguishing between the probabilities $\Pr[|X| \leq 1]$ and $\Pr[|X| < 1]$. This obstacle appeared in previous works as well, and is probably the reason for which the `barrier' of $3/8$ (which is the tight lower bound for $\Pr[|X|<1]$) was not beaten for almost 25 years, until the work of Boppana and Holzman~\cite{BH17}.

As a result, `hard' cases for our proof are not only tightness examples for the conjecture, but also $X$'s for which $\Pr[|X|<1]$ is small.
	We list three such examples of Rademacher sums:
	\begin{enumerate}
		\item $X=(x_1+x_2)/\sqrt{2}$, and more generally, $X=\sum a_i x_i$ with $\var(X)=1$ and
		\begin{equation}\label{Eq:Aux-Hard-case}
		a_1 + \min_{x \in \left\{-1,1\right\}^{[n]\setminus \{1\}}} \left|\sum_{i=2}^{n} a_i x_i\right| > 1.
		\end{equation}
				\item $X = \frac{1}{2}\sum_{i=1}^{4} x_i$.
		\item $X = \frac{1}{3}\sum_{i=1}^{9} x_i$.
	\end{enumerate}
	Rademacher sums $X$ that belong to the first class are tightness examples for Theorem~\ref{thm:main}, in the sense that $\Pr[|X|\leq 1]=1/2$. These are the only tightness examples we are aware of.
	The two latter classes are not tightness cases of the conjecture, but rather satisfy $\Pr[|X| < 1] < 1/2$, and inevitably complicate the proof. For example, in the third case, $\Pr[|X| < 1]=\frac{63}{128} < 0.493$, which demonstrates that the improved Berry-Esseen bound we prove in Section~\ref{sec:BE} is almost optimal. Indeed, while the bound implies that $\Pr[|X| < 1] \geq 1/2$ holds whenever $\max_i |a_i| \leq 0.31$, the example shows that this assertion fails when $\max |a_i|=1/3$.

\subsection{Structure of the proof}

The proof of Theorem~\ref{thm:main} is split into seven cases, which we shortly overview:


\paragraph{Case~1: $a_1 \leq 0.31$.} This case is covered by the improved Berry-Esseen bound for Rademacher sums presented in Section~\ref{sec:BE}.

\paragraph{Case~2: $a_1 + a_2 \geq 1$.} This case is covered by the semi-inductive argument (which uses the `stopping time' method), and is presented in Section~\ref{sec:induction}.

\paragraph{Case~3: $a_1 \geq 0.55$ and $a_1 + a_2 \leq 1$.} The proof in this case combines the `segment comparison' argument (i.e., Theorem~\ref{thm:seg_compare_intro}) with Chebyshev's inequality. The proof in this case is a simple example of the proof strategy in some the following cases, and so we slightly detail about it.

By Lemma~\ref{lem:nm}, applied with $m=1$, in order to verify $\Pr[|X| \leq 1] \geq 1/2$, it suffices to show
\begin{equation}\label{Eq:Prelim-Aux1}
\Pr[|X'| \leq t] > \Pr[|X'| > 1/t],
\end{equation}
 where $X',t$ are as defined in~\eqref{Eq:Prelim-Eliminate-one}. Since $a_2'$ -- the largest weight of $X'$ -- satisfies $a_2' \leq t$ (which follows from the condition $a_1+a_2 \leq 1$), Theorem~\ref{thm:seg_compare_intro} implies that $\Pr[|X'| \leq t] = \Omega(t)$. As Chebyshev's inequality yields $\Pr[|X'| > 1/t] \leq t^2$,~\eqref{Eq:Prelim-Aux1} follows if $t$ is sufficiently small, that is, if $a_1$ is sufficiently large. This argument applies when $a_1 \geq 0.55$, and is presented in Section~\ref{sec:055}.

\paragraph{Case~4: $a_1 \in [0.5,0.55]$ and $a_1 + a_2 \leq 1$.} The proof in this case splits according to whether $a_2$ is `large' or `small'. If $a_2$ is small, then the method of the previous case is sufficient. If $a_2$ is large, we eliminate two variables (by applying Lemma~\ref{lem:nm} with $m=2$) and prove the resulting inequality using Theorem~\ref{thm:seg_compare_intro} and the refined Chebyshev inequality (i.e., Proposition~\ref{prop:Intro-Chebyshev}). This case is presented in Section~\ref{sec:0.5<a_1<0.55}.

\paragraph{Case~5: $a_1 \in [0.31, 0.5]$ and $a_1 + a_2 + a_3 \leq 1$.} The proof in this case splits according to the sizes of $a_2$ and $a_3$.

If either of $a_2$ or $a_3$ is sufficiently small, then after elimination of one or two variables (respectively), the problem is reduced to a probabilistic inequality concerning a Rademacher sum with `sufficiently small' weights, and follows from the improved Berry-Esseen inequality.

Otherwise, we eliminate three variables and prove the assertion using Theorem~\ref{thm:seg_compare_intro} and Proposition~\ref{prop:Intro-Chebyshev}.
This case is demonstrated in Section~\ref{sec:remaining} and treated in detail in Appendix~\ref{sec:31big}.

\paragraph{Case~6: $a_1 \in [0.387, 0.5]$ and $a_1 + a_2 + a_3 \geq 1$.} The proof method in this case is superficially similar to that of the previous case. However, a subtle difference in the details makes this case simpler to handle. The proof in this case is demonstrated in Section~\ref{sec:remaining} and treated in detail in Appendix~\ref{sec:39geq}.

\paragraph{Case~7: $a_1 \in [0.31, 0.387]$ and $a_1 + a_2 + a_3 \geq 1$.} The proof in this case splits according to whether there exists some $k\geq 4$ with a `medium-sized' $a_k$.

If there is no such $a_k$, then the weights are partitioned into `large' ones and `small' ones. If there are at most four large weights, then by eliminating the four variables with largest weight, we reduce the problem to a probabilistic inequality concerning a Rademacher sum with `sufficiently small' weights that can be handled easily. Otherwise, we eliminate five variables and show that the assertion follows from  Proposition~\ref{prop:Intro-Chebyshev} and a `light' semi-inductive argument. The latter part is however somewhat cumbersome, as after eliminating five variables, we have to deal with $2^5=32$ summands simultaneously.

In the case where there exists a medium-sized $a_k$, we use an explicit bijection to prove a special segment comparison lemma that holds for it, which in turn allows deducing the assertion using Theorem~\ref{thm:seg_compare_intro} and Proposition~\ref{prop:Intro-Chebyshev}. The proof in this case is demonstrated in Section~\ref{sec:remaining} and treated in detail in Appendix~\ref{sec:0.31<a_1<0.387}.

\medskip \noindent Combination of the seven cases with induction over $n$ (where the inductive assumption is used in Cases 2 and 7), completes the proof of Theorem~\ref{thm:main}.


\section{Local Concentration Inequalities for Rademacher Sums}\label{sec:comparison}

In this section we present two concentration inequalities, that allow comparing the probabilities $\Pr[X \in I]$ and $\Pr[X \in J]$, where $X$ is a Rademacher sum and $I,J$ are segments or rays. Both results are used extensively throughout the paper. The first is a local concentration inequality:

\begin{theorem}[segment comparison]\label{thm:seg_compare}
	Let $X = \sum_{i=1}^{n} a_{i} x_{i}$, and write $M=\max_i |a_i|$. For all $A, B, C, D \in \mathbb{R}$ such that
		\begin{equation}\label{Eq:Comparison_condition_general}
		|A| \leq \min(B,C), \qquad 2M \leq C-A, \qquad \mbox{and} \qquad D-C + \min(2M, D-B) \leq B-A,
		\end{equation}
	one has
		\begin{equation}\label{eq:seg_compare}
		\Pr[X \in \hseg{C}{D}] \leq \Pr[X \in \hseg{A}{B}].
		\end{equation}
\end{theorem}

The assertion of Theorem~\ref{thm:seg_compare} holds for other types of segments as well; see Appendix~\ref{app:sub:other-types}.

\medskip We note that inequalities of the same type were obtained by the authors in~\cite{KK17}, where they were used to obtain an alternative proof of another local tail inequality due to Devroye and Lugosi~\cite{DL08} and to study analytic properties of linear threshold functions. While the inequalities in~\cite{KK17} are qualitative (i.e., of the form $\Pr[X \in \hseg{C}{D}] \leq c \Pr[X \in \hseg{A}{B}]$ for some non-optimal constant $c$), for our purposes here a more exact inequality is required. Such an inequality is given in Theorem~\ref{thm:seg_compare}, which strictly supersedes~\cite[Lemma 3.1]{KK17}.

\medskip The usefulness of `segment comparison' in the proof of Tomaszewski's conjecture is apparent, as the conjecture itself can be rephrased as a segment comparison inequality:
\begin{equation}\label{Eq:Toma-aux}
\hpr{X}{1}{\infty} \leq \hpr{X}{0}{1}.
\end{equation}
However, Theorem~\ref{thm:seg_compare} alone is not sufficient for our needs since it allows deducing $\Pr[X \in I] \leq \Pr[X \in J]$ only for segments $I,J$ that satisfy, in particular, $|I| \leq |J|$.

\medskip
The second result we present is a simple-yet-powerful generalization of the classical Chebyshev's inequality, which allows handling cases where $|I|>|J|$. For example, it enables to deduce $\hpr{X}{0}{1} \geq \hpr{X}{\sqrt{2}}{\infty}$, which reminds of~\eqref{Eq:Toma-aux} but is of course much weaker.
	\begin{lemma}\label{lem:cheby}
		Let $X$ be a symmetric (around $0$) random variable with $\var(X) = 1$, and let
		\[
			0 = c_0 \leq c_1 \leq \ldots \leq c_n = 1 = d_0 \leq d_1 \leq \ldots \leq d_m \leq d_{m+1}=\infty.
		\]
		Then
		\begin{equation}\label{eq:cheby_our}
		\sum_{i=0}^{n-1} (1-c_i^2) \hpr{X}{c_i}{c_{i+1}} \geq \sum_{i=1}^{m} (d_i^2-d_{i-1}^2) \Pr[X \geq d_i],
		\end{equation}
		and similarly,
		\begin{equation}\label{eq:cheby_our2}
		\sum_{i=0}^{n-1} (1-c_i^2) \hpr{X}{c_i}{c_{i+1}} \geq \sum_{i=1}^{m} (d_i^2-1) \hpr{X}{d_i}{d_{i+1}}.
		\end{equation}
	\end{lemma}
While we did not find this result in the literature, it is presumably known or even folklore. We note that a variant of Lemma~\ref{lem:cheby} was used in the recent work of Dvo{\v{r}}{\'{a}}k et al.~\cite{DHT20}

\medskip Neither Theorem~\ref{thm:seg_compare} nor Lemma~\ref{lem:cheby} is sufficient for tackling Tomaszewski's conjecture. However, a combination of these tools allows proving the conjecture in several significant cases.

\paragraph{Organization.}
The proof of Theorem~\ref{thm:seg_compare} uses an explicit injection, which maps the event on the left hand side of~\eqref{eq:seg_compare} to the event corresponding to the right hand side. We present several auxiliary bijections that will be used to construct our injection in Section~\ref{ssec:inj-maps}, and then we prove Theorem~\ref{thm:seg_compare}
in Section~\ref{ssec:seg-compare}. The simple and standard proof of Lemma~\ref{lem:cheby} is presented in Appendix~\ref{ssec:cheby}.


\subsection{Auxiliary bijections}\label{ssec:inj-maps}
\newcommand{\mathrm{PF}}{\mathrm{PF}}
\newcommand{\mathrm{SF}}{\mathrm{SF}}
\newcommand{\mathrm{RF}}{\mathrm{RF}}
\newcommand{\mathrm{Domain}}{\mathrm{Domain}}

In this subsection we present three bijections on the discrete cube $\{-1,1\}^n$ (i.e., bijections from the discrete cube to itself) that satisfy certain desired properties. The first two bijections were already introduced in~\cite{KK17} and are presented here for the sake of completeness

\subsubsection{Prefix flip}


\begin{lemma}[Prefix flip]\label{lem:prefix-flip}
		Let $a = (a_1, \ldots, a_n)$ be a sequence of positive real numbers, let $M=\max_i a_i$ and let $Q \geq 0$. There exists a bijection $\func{\mathrm{PF}_{a, Q}}{\left\{-1,1\right\}^n}{\left\{-1,1\right\}^n}$ such that for any $v \in \left\{-1,1\right\}^n$ with
		\begin{equation}\label{eq:pf-assumption}
		X(v)\mathrel{\mathop:}= \sum_{i=1}^{n} a_i v_i \geq Q/2,
		\end{equation}
		the image $w=\mathrm{PF}_{a, Q}(v)$ satisfies
		\begin{equation}\label{Eq:Comp-Aux1}
		X(w)=\sum_{i=1}^{n} a_i w_i \in (X(v)-Q-2M,X(v)-Q].
		\end{equation}
\end{lemma}

\paragraph{Construction of $\mathrm{PF}_{a, Q}$.} Let $v \in \left\{-1,1\right\}^n$ satisfy~\eqref{eq:pf-assumption}. Let $k>0$ be minimal so that $\sum_{j=1}^{k} a_j v_j \geq Q/2$. Define $w=\mathrm{PF}_{a, Q}(v)$ by $w_i = -v_i$ for $i \leq k$, and $w_i = v_i$ for $i > k$.

\medskip \noindent We prove that $\mathrm{PF}_{a, Q}$ satisfies the requirements of the lemma in Appendix~\ref{ssec:prefix-flip}.
We call the function $\mathrm{PF}_{a, Q}$ a \emph{prefix flip}. 


\subsubsection{Single coordinate flip}

	\begin{lemma}[Single coordinate flip]\label{lem:single-flip}
		Let $a = (a_1, \ldots, a_n)$ be a sequence of positive real numbers and let $M=\max_i a_i$ and $m = \min_i a_i$. There exists a bijection $\func{\mathrm{SF}_{a}}{\left\{-1,1\right\}^n}{\left\{-1,1\right\}^n}$ such that for any $v \in \left\{-1,1\right\}^n$  with
		\begin{equation}\label{eq:sf-assumption}
		X(v)\mathrel{\mathop:}= \sum_{i=1}^{n} a_i v_i > 0,
		\end{equation}
		the image $w=\mathrm{SF}_{a}(v)$ is obtained from $v$ by flipping a single coordinate from $1$ to $(-1)$, and in particular, satisfies
		\[
		X(w)=\sum_{i=1}^{n} a_i w_i \in [X(v)-2M,X(v)-2m].
		\]
	\end{lemma}

\paragraph{Construction of $\mathrm{SF}_{a}$.} Let $v \in \left\{-1,1\right\}^n$ satisfy~\eqref{eq:sf-assumption}. Further assume that $a_1 \geq \ldots \geq a_n > 0$. Let $k > 0$ be the minimal value that maximizes the quantity $\sum_{j=1}^{k} v_j$. Define $w=\mathrm{SF}_{a}(v)$ by $w_i = v_i$ for all $i \neq k$, and $w_k = -v_k$.
	
\medskip \noindent We prove that $\mathrm{SF}_{a}$ satisfies the requirements of the lemma in Appendix~\ref{ssec:single-flip}. We call the function $\mathrm{SF}_{a}$ a \emph{single coordinate flip}.

\subsubsection{Recursive flip}
	\begin{lemma}[Recursive flip]\label{lem:recursive-flip}
		Let $a = (a_1, \ldots, a_n)$ be a sequence of positive real numbers and let $M=\max_i a_i$ and $m = \min_i a_i$. There exists a bijection $\func{\mathrm{RF}_{a}}{\left\{-1,1\right\}^n}{\left\{-1,1\right\}^n}$ such that any $v \in \left\{-1,1\right\}^n$ and its image $w = \mathrm{RF}_a(v)$ satisfy:
		
		\medskip\indent \textbf{1)} If $X(v) > 0$ then $X(w) \in [X(v)-2M, X(v)-2m]$;

		\medskip\indent \textbf{2)} If $X(v) \leq 0$, then either $w=-v$ (and $X(w)=-X(v)$) or $X(w) \in [X(v) -2M, 0)$,
	
		\medskip \noindent where $X(u) \mathrel{\mathop:}= \sum_{i=1}^{n} a_i u_i$ for $u \in \left\{-1,1\right\}^n$.
	\end{lemma}


\paragraph{Construction of $\mathrm{RF}_a$.}
Define the auxiliary injection $\func{F}{\set{v\in\left\{-1,1\right\}^n}{X(v)>0}}{\left\{-1,1\right\}^n}$ by
\[
F(v)=-\mathrm{SF}_{a}(v),
\]
and note that $F$ is not defined for $\set{v}{X(v) \leq 0}$.
Define $\mathrm{RF}_{a}:\left\{-1,1\right\}^n \to \left\{-1,1\right\}^n$ by
\[
\mathrm{RF}_{a}(v) =
\begin{cases}
\phantom{-}\mathrm{SF}_{a}(v), & \quad X(v)>0 \\
-(F^{-1})^{k}(v), & \quad X(v)\leq 0
\end{cases},
\]
where $k\geq 0$ is minimal such that $(F^{-1})^{k+1}(v)$ does not exist, i.e., $(F^{-1})^{k}(v) \notin \mathrm{Image}(F)$.

\medskip
Informally, after defining $\mathrm{RF}_a(v)$ for all $\set{v}{X(v)>0}$ using a single coordinate flip, we would like to define $\mathrm{RF}_a(v)$ for any other $v$ as a simple negation: $\mathrm{RF}_a(v)=-v$. However, this may breach the injectivity if there exists some $w$ such that $X(w)>0$ and $\mathrm{SF}_a(w)=-v$. In such a case, we define $v'=\mathrm{SF}_a^{-1}(-v)$ and check whether $-v'$ is `vacant' (i.e., does not collide with any $\mathrm{SF}_a(z)$). If it is vacant, we set $\mathrm{RF}_a(v)=-v'$; otherwise, we continue applying $\mathrm{SF}_a^{-1}$ and negating until we reach a vacant value. The auxiliary function $F$ combines application of $\mathrm{SF}_a$ with negation, and hence, in each step we apply $F^{-1}$, as stated in the definition. We note that this construction is reminiscent of the way of constructing a bijection from two injections, used in the classical proof of the Cantor-Schr\"oder-Bernstein theorem by J. K\"onig.

\medskip 
We call the function $\mathrm{RF}_{a}$ a \emph{recursive flip}.	A concrete example that demonstrates the way $\mathrm{RF}_a$ works is presented in Appendix~\ref{app:misc:RF}, and the proof that $\mathrm{RF}_{a}$ satisfies the assertion of the lemma is presented in Appendix~\ref{ssec:recursive-flip}.



	\subsection{Proof of Theorem~\ref{thm:seg_compare}}\label{ssec:seg-compare}
	The proof of Theorem~\ref{thm:seg_compare} is split into two different arguments, corresponding to how the condition $D-C + \min(D-B, 2M) \leq B-A$ in~\eqref{Eq:Comparison_condition_general} is realized -- either as $D-C+2M \leq B-A$, or as $D-C + (D-B) \leq B-A$. We formulate these two cases as two separate lemmas.
	\begin{lemma}\label{lem:seg-compare1}
		Let $X = \sum_{i=1}^{n} a_{i} x_{i}$ be a Rademacher sum, and write $M=\max_i a_i$. For any $A, B, C, D \in \mathbb{R}$ such that
		\begin{equation}\label{Eq:Aux-Compare-proof1}
		\min(|A|, |B|) \leq C \qquad \mbox{and} \qquad D-C+2M \leq B-A,
		\end{equation}
		we have
		\begin{equation}\label{eq:seg-compare1}
			\Pr[X \in \hseg{C}{D}] \leq \Pr[X \in \hseg{A}{B}].
		\end{equation}
	\end{lemma}
	
	\begin{lemma}\label{lem:seg-compare2}
		Let $X = \sum_{i=1}^{n} a_{i} x_{i}$ be a Rademacher sum, and write $M=\max_i a_i$. For any $A, B, C, D \in \mathbb{R}$ such that
		\begin{equation}\label{Eq:Aux-Compare-proof2}
		|A| \leq C \qquad \mbox{and} \qquad 2\max(M, D-B) \leq C-A,
		\end{equation}
		we have
		\begin{equation}\label{eq:seg-compare2}
			\Pr[X \in \hseg{C}{D}] \leq \Pr[X \in \hseg{A}{B}].
		\end{equation}
	\end{lemma}
	The combination of Lemmas~\ref{lem:seg-compare1} and~\ref{lem:seg-compare2} immediately implies Theorem~\ref{thm:seg_compare}. Notice that the assumptions in both lemmas are slightly weaker than the assumptions in Theorem~\ref{thm:seg_compare}; this weakening of the assumptions will be needed in the sequel.
	
\begin{remark}
	The assertions of Lemmas~\ref{lem:seg-compare1} and~\ref{lem:seg-compare2} hold for other types of segments as well; see Appendix~\ref{app:sub:other-types}.
\end{remark}	
	
\paragraph{Notation.}
		Given a Rademacher sum $X = \sum_{i=1}^{n} a_i x_i$ and a quadruple $A,B,C,D\in \mathbb{R}$ that satisfies either~\eqref{Eq:Aux-Compare-proof1} or~\eqref{Eq:Aux-Compare-proof2} (so that either Lemma~\ref{lem:seg-compare1} or Lemma~\ref{lem:seg-compare2} can be applied), or $D \leq C$, we write $\hseg{C}{D} \prec_X \hseg{A}{B}$. Using this notation, the lemmas can be rewritten as the deduction
		\[
			\hseg{C}{D} \prec_X \hseg{A}{B} \qquad  \implies \qquad \hpr{X}{C}{D} \leq \hpr{X}{A}{B}.
		\]
		
\subsubsection{Proof of Lemma~\ref{lem:seg-compare1}}
	
	\begin{proof}[Proof of Lemma~\ref{lem:seg-compare1}]
		We first show that we may assume $|A| \leq |B|$, so that~\eqref{Eq:Aux-Compare-proof1} is upgraded to
		\begin{equation}\label{Eq:Aux-Compare-proof3}
			|A| \leq C \qquad \mbox{and} \qquad D-C+2M \leq B-A.
		\end{equation}

\medskip\noindent\textbf{Upgrading to~\eqref{Eq:Aux-Compare-proof3}.}
		If $A > B$, Lemma~\ref{lem:seg-compare1} is vacant. Otherwise, if $|A| \leq |B|$ we are done. In the remaining case, we exchange $A,B,C,D$ by $-B, -A, C, D$, so that~\eqref{Eq:Aux-Compare-proof3} (and hence~\eqref{Eq:Aux-Compare-proof1}) are satisfied by the new quadruple, and conclude~\eqref{Eq:Aux-Compare-proof1} by noting $\hpr{X}{A}{B} = \hpr{X}{-B}{-A}$.
		
	
	
	
	
	

	
		
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	

\medskip\noindent\textbf{Proving~\eqref{eq:seg-compare1}.}
		We assume $A,B,C,D$ satisfy~\eqref{Eq:Aux-Compare-proof3} and prove~\eqref{eq:seg-compare1}

		We may also assume $Q \mathrel{\mathop:}= D-B>0$, as otherwise $D\leq B$, and $[C,D] \subseteq [A,B]$ implies~\eqref{eq:seg-compare1}.
		
		Consider the prefix flip map $\mathrm{PF}_{a,Q}$. For any $v \in \left\{-1,1\right\}^n$ with $X(v) \in [C,D]$, we have $X(v) \geq Q/2$, since by~\eqref{Eq:Aux-Compare-proof3},
		\[
		Q =D-B \leq D-B + 2M \leq C-A \leq 2C.
		\]
		Hence, by Lemma~\ref{lem:prefix-flip}, for any such $v$, the image $w=\mathrm{PF}_{a, Q}(v)$ satisfies
		\[
		X(w) \in (X(v)-Q-2M, X(v)-Q].
		\]
		As $C \leq X(v) \leq D$ and $Q=D-B$, this implies $X(w) \in (A, B]$. Finally, since $X(w)=B$ may occur only if $X(v)=D$, the injectivity of $\mathrm{PF}_{a, Q}$ implies
		\begin{equation}\label{eq:semi-compare}
			\Pr[X \in \left[C,D\ri\rangle] \leq \Pr[X \in \left(A, B\ri\rangle],
		\end{equation}
		which is even slightly stronger than the assertion~\eqref{eq:seg-compare1}. This completes the proof.
	\end{proof}

\subsubsection{Proof of Lemma~\ref{lem:seg-compare2}}

The proof of the lemma uses an explicit injection which we hereby describe.

\paragraph{Notation.}
Let $X(x)=\sum_{i=1}^n a_i x_i$ be a Rademacher sum, and $A,B,C,D,M$ be real numbers that satisfy the conditions of Lemma~\ref{lem:seg-compare2}. Note that we may assume $D>B$, as otherwise, the assertion of the lemma holds trivially.

We partition the coefficients $\{a_i\}$ into `large' and `small' ones. Let
\[
L = \left\{ \given{i}{a_{i} \geq (D-B)/2} \right\}, \qquad S = [n] \setminus L.
\]
Note that this partition depends only on the fixed parameters $\{a_i\}$ and $A,B,C,D$.

In addition, for a subset $I \subseteq [n]$ and for $x \in \left\{-1,1\right\}^{n}$, we write $x_I \mathrel{\mathop:}= \restrict{x}{I}$ and $a_I \mathrel{\mathop:}= \restrict{a}{I}$, and correspondingly, $a_I \cdot x_I = \sum_{i \in I} a_{i} x_{i}$.

\theoremstyle{definition}
\newtheorem*{definition*}{Definition}

\begin{definition*}
Let $v \in \left\{-1,1\right\}^n$ be such that $X(v) \in [C,D]$. We define $u=f(v) \in \left\{-1,1\right\}^n$ in two steps. First, we denote
\[
w=g(v)=(\mathrm{RF}_{a_L}(v_L), v_S) \qquad \mbox{and} \qquad Q_{v} = (D-B)-(X(v)-X(w)).
\]
Then, we set
\[
u =f(v)=
\begin{cases}
w, & \quad Q_v \leq 0, \\
(w_L, \mathrm{PF}_{a_S, Q_{v}}(w_S)), & \quad Q_v>0.
\end{cases}
\]
\end{definition*}

\paragraph{Motivation.} We prove Lemma~\ref{lem:seg-compare2} by showing that $f\colon v\mapsto u$ injectively maps any $v$ with $X(v) \in [C,D]$ to some $u$ with $X(u) \in [A,B]$.
The single-coordinate-flip map of the large coordinates, $\mathrm{SF}_{a_L}$, seemingly has the same property, that is, maps any $v'$ with $X(v') \in [C,D]$ to some $w'$ with $X(w') \in [A,B]$.

However, $\mathrm{SF}_{a_L}$ might fail to flip a single coordinate when $a_L \cdot v'_{L} \leq 0$. In such a case, we have $a_S \cdot v'_{S} \geq C \geq (D-B)/2$, and a prefix-flip map $\mathrm{PF}_{a_S, D-B}\colon v' \mapsto u'$ does satisfy $X(u') \in [A,B]$.
This reasoning, of mapping $v'$ into either $w'$ or $u'$, proves that
\[
\hpr{X}{C}{D} \leq 2\cdot\hpr{X}{A}{B},
\]
as it results in a 2-to-1 map (each of $v'\mapsto w'$ and $v'\mapsto u'$ is injective).

We wish to show the stronger inequality $\hpr{X}{C}{D} \leq \hpr{X}{A}{B}$. For this, we construct $f$ in two steps. At the first step we apply on the large coordinates the recursive-flip $\mathrm{RF}_{a_L}$ (which is closely related to $\mathrm{SF}_{a_L}$) to obtain $w$. Then, at the second step, conditioned on data available in $w_L$, we choose whether to apply a prefix flip on the small coordinates or not. This results in a single 1-to-1 map. The usage of $\mathrm{RF}_{a_L}$ instead of $\mathrm{SF}_{a_L}$ is important in order for $w_L$ to have guaranteed properties, even when $a_L \cdot v'_L \leq 0$.

\begin{proof}[Proof of Lemma~\ref{lem:seg-compare2}]
		Let $X = \sum_{i=1}^{n} a_i x_i$ and $A,B,C,D,M$ be as in the statement of the lemma, and define the function $f$ on the set $\set{v}{X(v) \in [C,D]}$ as described above.
		
\paragraph{Why is $f$ injective?}
		To compute the inverse map $u \mapsto v$, first consider $u_L$ and apply the inverse recursive flip $\mathrm{RF}_{a_L}^{-1}$ to recover $v_L$. Then, compute $Q_{v}$ (which depends only on $v_L$ and not on $v_S$). Now, it is clear from the definition of $f$ that we have
		\[
		v =
		\begin{cases}
		(\mathrm{RF}_{a_L}^{-1}(u_L), u_S), & \quad Q_v \leq 0, \\
		(\mathrm{RF}_{a_L}^{-1}(u_L), \mathrm{PF}_{a_S, Q_{v}}^{-1}(u_S)), & \quad Q_v>0.
		\end{cases}
		\]

\paragraph{Why is $f$ into $[A,B]$?}
		Let $v$ satisfy $X(v) \in [C,D]$. We want to show that $u=f(v)$ satisfies $X(u) \in [A,B]$.
		We consider two cases.
		
		\paragraph{Case~1:  $a_L\cdot v_L > 0$.} In this case, since for all $i \in L$ we have $ (D-B)/2 \leq a_i \leq M$, the first property of the recursive flip (presented in Lemma~\ref{lem:recursive-flip}) implies
		\begin{equation}\label{Eq:Aux-Compare-proof4}
		X(w) \in [X(v) - 2M, X(v) - (D-B)].
		\end{equation}
		In particular, we have $Q_{v} = (D-B)-(X(v)-X(w)) \in [D-B-2M,0]$, and thus, by the definition of $f$, we set $u=f(v)=w$. By~\eqref{Eq:Aux-Compare-proof4}, we have
		\[
			X(u) = X(w) \in [X(v) - 2M, X(v) - (D-B)] \subseteq [C-2M,D-(D-B)] \subseteq [A,B],			
		\]
		where the last inclusion uses the assumption $2M \leq C-A$.
		
		\paragraph{Case~2:  $a_L\cdot v_L \leq 0$.} In this case, the second property of $\mathrm{RF}_{a_L}$ (in Lemma~\ref{lem:recursive-flip}) implies
		\begin{equation}\label{Eq:Aux-Compare-proof4.5}
		a_L\cdot w_L \in [a_L\cdot v_L-2M, -a_L\cdot v_L],
		\end{equation}
		and hence,
		\[
		Q_v=(D-B)-(X(v)-X(w) \in (D-B) - [2 a_L \cdot v_L, 2M] = [D-B-2M, D-B-2a_L \cdot v_L].
		\]
		We further subdivide this case into two sub-cases.
		
		\paragraph{Case~2a: $Q_v\leq 0$.} In this case, we have $Q_v \in [D-B-2M,0]$, and hence,
		\[
		X(v)-X(w) = (D-B)-Q_v \in [D-B,2M].
		\]
		As $X(v) \in [C,D]$, this implies
		\[
		X(w) \in [C-2M,D-(D-B)] \subseteq [A,B],
		\]
		where the last inclusion follows from the assumption $2M \leq C-A$.
		
		By the definition of the function $f$, we have $u=w$, and so, $X(u)=X(w) \in [A,B]$.

		\paragraph{Case~2b: $Q_v> 0$.} In this case, by the definition of $f$, we have $u=f(v)=(w_L, \mathrm{PF}_{a_S, Q_{v}}(w_S))$, and hence, we would like to apply
		Lemma~\ref{lem:prefix-flip} to the function $\mathrm{PF}_{a_S,Q_v}:w_S \mapsto u_S$. To this end, we have to prove
		\begin{equation}\label{Eq:Aux-Compare-proof5}
		a_S \cdot w_S \geq Q_{v}/2.
		\end{equation}
		To prove~\eqref{Eq:Aux-Compare-proof5}, note that the assumptions $2(D-B) \leq C-A$ and $|A| \leq C$ imply
		\begin{equation}\label{Eq:Aux-Compare-proof6}
		2C \geq C-A \geq 2(D-B) \geq D-B.
		\end{equation}	
		In addition, by~\eqref{Eq:Aux-Compare-proof4.5} we have
		\begin{equation}\label{Eq:Aux-Compare-proof7}
		X(v)-X(w)=a_L \cdot v_L -a_L \cdot w_L \geq 2a_L \cdot v_L.
		\end{equation}
		Since $a_S \cdot w_S = a_S \cdot v_S$ and $a_S \cdot v_S + a_L \cdot v_L = X(v) \in [C,D]$,~\eqref{Eq:Aux-Compare-proof6} and~\eqref{Eq:Aux-Compare-proof7} imply
		\[
		a_S \cdot w_S = X(v)- a_L \cdot v_L \geq C - a_L\cdot v_L \geq (D-B - (X(v)-X(w)))/2=Q_v/2,
		\]
		proving~\eqref{Eq:Aux-Compare-proof5}.
		
		\medskip As stated above,~\eqref{Eq:Aux-Compare-proof5} allows us to apply Lemma~\ref{lem:prefix-flip} to the function $\mathrm{PF}_{a_S,Q_v}:w_S \mapsto u_S$. Since $M'=\max_{i \in S} a_i \leq (D-B)/2$, the lemma implies
		\begin{align*}
		X(u)-X(w) &= a_S \cdot u_S - a_S \cdot w_S	\in (-2M'-Q_{v}, -Q_{v}] \\
		&\subseteq ((X(v)-X(w)) - 2(D-B), (X(v)-X(w)) - (D-B)] \\
		&= (X(v)-X(w)) + (-2(D-B), -(D-B)].
		\end{align*}
		Therefore,
		\[
		X(u) = X(v) + (X(w)-X(v)) + (X(u)-X(w)) \in X(v) + (- 2(D-B), -(D-B)].
		\]
		Since $X(v) \in [C,D]$, we have
		\[
		X(u) \in (C-2(D-B),D-(D-B)] \subseteq (A,B],
		\]
		where the last inclusion follows from the assumption $2(D-B)\leq C-A$.

		\paragraph{What happens to the endpoints?}
		Notice that in all cases, $X(u)=A$ may hold only if $X(v)=C$, and $X(u)=B$ may hold only if $X(v)=D$. Hence, the assertion of the lemma:
		\[
		\Pr[X \in \hseg{C}{D}] \leq \Pr[X \in \hseg{A}{B}].
		\]
		follows from the injectivity of $f\colon v \mapsto u$.
	\end{proof}

	
\section{Improved Berry-Esseen Type Inequalities for Rademacher Sums: Proving Theorem~\ref{thm:main} for \tops{$a_1 \leq 0.31$}}\label{sec:BE}
	A natural approach toward proving Tomaszewski's conjecture in the case where all the coefficients $a_i$ are small, is using the  classical Berry-Esseen theorem~(\cite{Berry41,Esseen42}), which allows approximating a sum of independent random variables by a Gaussian (i.e., a normally distributed random variable).
	\begin{theorem}[Berry-Esseen]
		Let $X_1,X_2,\ldots,X_n$ be independent random variables, such that $\forall i:\mathbb{E}[|X_i|^3]<\infty$. Let $X=\sum_{i=1}^n X_i$. Then for all $x$,
		\begin{equation}\label{Eq:Aux-BE1}
		\left|\Pr\left[\frac{X}{\sqrt{\var(X)}} \leq x\right]-\Pr[Z \leq x]\right| \leq C \cdot \frac{\sum_{i=1}^n \mathbb{E}|X_i|^3}{\var(X)^{3/2}},
		\end{equation}
		where $Z \sim N(0,1)$ is a standard Gaussian and $C$ is an absolute constant.
	\end{theorem}
\noindent	For a Rademacher sum $X=\sum a_i x_i$ with $\var(X)=1$, the theorem yields
	\[
	\left|\Pr[X \leq x]-\Pr[Z \leq x]\right| \leq C \cdot \sum_i a_i^3 \leq C \cdot \max_i |a_i| \sum_i a_i^2 =  C \cdot \max_i |a_i|,
	\]
	and consequently,
	\begin{equation}\label{Eq:Aux-BE2}
	\left|\Pr[|X| \leq 1]-\Pr[|Z| \leq 1]\right| \leq 2C \cdot \max_i |a_i|.
	\end{equation}
	The best currently known upper bound on the constant $C$ in~\eqref{Eq:Aux-BE1} is $C \leq 0.56$, obtained in~\cite{Shevtsova10}. Plugging it into~\eqref{Eq:Aux-BE2} and noting that
	$\Pr[|Z|\leq 1] \geq 0.682$,~\eqref{Eq:Aux-BE2} implies Tomaszewski's conjecture in the range $\max_i |a_i| \leq 0.162$, as was noted by Bentkus and Dzindzalieta~\cite{BD15}.
	
	Using merely the general form of the Berry-Esseen theorem, this result cannot be improved much. Indeed, it was shown by Esseen~\cite{Esseen56} that the constant $C$ in~\eqref{Eq:Aux-BE1} satisfies $C>0.409$, and hence, the best one can hope for by plugging an improved $C$ into~\eqref{Eq:Aux-BE2} is extending the range to $\max_i |a_i| \leq 0.182/0.818 \leq 0.223$.
	
	\medskip In this section we show that refined Berry-Esseen type bounds can be obtained in the special case where $X$ is a Rademacher sum.
	
	Our starting point is a smoothing inequality of Prawitz~\cite{pra72} which allows obtaining bounds on the cumulative distribution function of a random variable $X$ (i.e., $\Pr[X \leq x]$), given partial knowledge of its characteristic function $\varphi_X(t)=\mathbb{E}[e^{itX}]$. Prawitz' inequality has many applications (see Section~\ref{sec:sub:Prawitz}). In particular, Prawitz himself suggested using his inequality to bound $|\Pr[X < x]-\Pr[Z < x]|$, and Shevtsova~\cite{Shevtsova10} used his strategy to prove the best currently known bound on the constant $C$ in the Berry-Esseen theorem.
	
	When $X$ is a Rademacher sum, the strategy of Prawitz can be refined, yielding significantly better bounds than in the general case. Specifically, we obtain the following technical result.
	\begin{proposition}\label{prop:Prawitz-Rademacher}
	Let $X = \sum_i a_i x_i$ be a Rademacher sum with $a_1 \geq a_2 \geq \ldots \geq a_n>0$ and $\var(X)=1$. Then for any $T>0$, $q \in [0,1]$, and $x \in \mathbb{R}$ we have
	\begin{align}\label{Eq:Our-Prawitz}
		\begin{split}
		\Pr[Z < x] - \Pr[X < x] &\leq
		\int_{0}^{q} \left|k(u,x,T)\right| g(Tu) \mrm{d}{u} +
		\int_{q}^{1} \left|k(u,x,T)\right| h(Tu) \mrm{d}{u} + \\
		&+ \int_{0}^{q} k(u,x,T) \exp(-(Tu)^2/2) \mrm{d}{u} +
		\int_{0}^{x} \frac{1}{\sqrt{2\pi}}\exp(-u^2/2) \mrm{d}{u},
		\end{split}
	\end{align}
where $k(u,x,T) = \frac{(1-u)\sin(\pi u - T u x)}{\sin(\pi u)} - \frac{\sin(T u x)}{\pi}$,
\[
g(v) =
\begin{cases}
\exp(-v^{2}/2) - \cos(a_1 v) ^ {1/a_1^2}, & a_1 v \leq \frac{\pi}{2}\\
\exp(-v^{2}/2)+1, & \mrm{otherwise}
\end{cases}
, \quad h(v) =
\begin{cases}
\exp(-v^{2}/2),					& a_1 v \leq \theta\\
(-\cos(a_1 v))^{1/a_1^2},	    & \theta \leq a_1 v \leq \pi\\
1,								& \mrm{otherwise}
\end{cases},
\]
$Z \sim N(0,1)$ is a standard Gaussian and $\theta=1.778 \pm 10^{-4}$ is the unique root of the function $y \mapsto \exp(-y^2/2)+\cos(y)$ in the interval $[0,\pi]$.	
\end{proposition}

While in this paper we bound ourselves to proving Proposition~\ref{prop:Prawitz-Rademacher}, it appears that one can obtain more general estimates about Rademacher sums using similar strategies; see Section~\ref{sec:open}.


\medskip Our first application of Proposition~\ref{prop:Prawitz-Rademacher} validates Tomaszewski's conjecture in the range $\max_i a_i \leq 0.31$ (compared to $0.16$ that can be obtained by the general Berry-Esseen bound):
\begin{proposition}\label{lem:be_toma}
	Let $X = \sum_i a_i x_i$ be a Rademacher sum with $\max_i a_i \leq 0.31$ and $\var(X)=1$. Then
	\begin{equation}\label{eq:small-toma2}
	\Pr[X < 1] \geq \Pr[Z < 1] - 0.09115,
	\end{equation}
	and consequently,
	\begin{equation}\label{eq:small-toma}
	\Pr[X < 1] \geq 0.7501, \qquad \Pr[|X| < 1] \geq 0.5002.
	\end{equation}
\end{proposition}

Proposition~\ref{lem:be_toma} follows from Proposition~\ref{prop:Prawitz-Rademacher} directly, by substitution of suitable parameters. We note that the condition $\max_i a_i \leq 0.31$ cannot be relaxed significantly. Indeed, this is demonstrated by $X = \frac{1}{3} \sum_{i=1}^{9} x_{i}$ having $\max_i a_i =1/3$ and $\Pr[|X| < 1] = \frac{63}{128} < 0.493$.

\medskip  Our second application of Proposition~\ref{prop:Prawitz-Rademacher} is a concrete estimate which we shall use in the proof of Tomaszewski's conjecture in the range $\max_i a_i \in (0.31, 0.5)$.
	\begin{proposition}\label{prop:ad-hoc2}
		Let $X = \sum_i a_i x_i$ be a Rademacher sum with $\max_i a_i \leq 0.22$ and $\var(X) = 1$. Then, for any $x \geq 0$, we have
		\begin{equation}\label{eq:ad-hoc2}
			\Pr[X \leq x] \geq \Pr[Z \leq x] - \max(0.084, \Pr[|Z| \leq a_1]/2),
		\end{equation}
		where $Z \sim N(0,1)$ is a standard Gaussian variable.
	\end{proposition}

\paragraph{Organization.}
In Section~\ref{sec:sub:Prawitz} we describe the inequality of Prawitz~\cite{pra72} and apply it to Rademacher sums, proving Proposition~\ref{prop:Prawitz-Rademacher}. In Section~\ref{sec:sub:BE-applications} we prove Propositions~\ref{lem:be_toma} and~\ref{prop:ad-hoc2}.
In Appendix~\ref{app:no-numeric} we show how to practically evaluate the bound~\eqref{Eq:Our-Prawitz} to a required precision.

\subsection{The smoothing inequality of Prawitz applied to Rademacher sums}
\label{sec:sub:Prawitz}

\subsubsection{Prawitz' inequality}

In~\cite{pra72}, H\r{a}kan Prawitz proposed a way for bounding the cumulative distribution function of a random variable $X$, in terms of partial information on its characteristic function $\varphi_X(t)=\mathbb{E}[e^{itX}]$. The main result of~\cite{pra72} (specifically,~\cite[(1b)]{pra72}) reads:
\begin{theorem}\label{thm:prawitz}
	Let $X$ be a real-valued random variable, and assume that the characteristic function $\varphi_X(t)=\be[\exp(i t X)]$ is given for $|t| \leq T$. Then for any $x \in \mathbb{R}$,
\begin{equation}\label{eq:prawitz1}
\Pr[X < x] \geq \frac{1}{2} - v.p.\int_{-T}^{T} e^{-ixu} \frac{1}{T}  K(-u/T) \varphi_X(u) \mrm{d}{u},
\end{equation}
where
\begin{equation}\label{eq:Ku}
K(u) = \frac{1-|u|}{2} + \frac{i}{2} \left( (1-|u|) \cot(\pi u) + \frac{\mrm{sgn}(u)}{\pi} \right).
\end{equation}
\end{theorem}
The notation $v.p. \int_{-T}^{T}$, which is an abbreviation for \emph{valeur principale} integral, has the meaning $\lim_{\epsilon \to 0^{+}} \left[ \int_{-T}^{-\epsilon} + \int_{\epsilon}^{T} \right]$. It is required, as $K(u) = \frac{i}{2u\pi}+O(1)$ around $u=0$, and a naive integral would diverge. Once using	$v.p. \int_{-T}^{T} = \lim_{\epsilon \to {0}} \left[ \int_{-T}^{-\epsilon} + \int_{\epsilon}^{T} \right]$, the integral in~\eqref{eq:prawitz1} converges, as $K$ satisfies $K(-u) + K(u) = O(1)$, and is multiplied by a function which is $C+O(u)$ around $u=0$.

\medskip
Theorem~\ref{thm:prawitz} has numerous applications in probability theory (e.g.,~\cite{BG97,GZ14}) and in statistics (e.g.,~\cite{BGZ97,BG02,HW04}). In particular, already in~\cite[Sec.~10]{pra72}, Prawitz suggested using his method for obtaining approximation by a Gaussian variable in terms of distance between characteristic functions. A few decades later, this strategy was used by Shevtsova (\cite{Shevtsova10}, see also~\cite{KS10}) to obtain the best currently known bound on the constant $C$ in the Berry-Esseen theorem.

For more information on Theorem~\ref{thm:prawitz} and its applications, see the survey~\cite{Bobkov16}.

\subsubsection{A refined inequality for Rademacher sums}

For a Rademacher sum $X = \sum_{i=1}^{n} a_{i} x_{i}$, the characteristic function $\varphi_X$ has the convenient form \begin{equation}\label{Eq:Aux-Prawitz1}
\varphi_{X}(t) = \mathbb{E}[e^{itX}] =\prod_{i=1}^{n} \cos(a_{i} t).
\end{equation}
Since~\eqref{Eq:Aux-Prawitz1} is defined for any $t \in \mathbb{R}$, for any $T>0$ we can substitute in~\eqref{eq:prawitz1} $u/T$ in place of $u$:
\begin{equation}\label{eq:prawitz}
\Pr[X < x] \geq \frac{1}{2} - v.p.\int_{-1}^{1} e^{-ixuT} K(-u) \varphi_X(uT) \mrm{d}{u}.
\end{equation}
Due to the symmetry of $X$ around $0$, we have $\varphi_{X}(-u) = \varphi_{X}(u) \in \mathbb{R}$. This, together with $\overline{K(-u)}=K(u)$, implies
	\[
		\Pr[X < x] \geq \frac{1}{2} - 2\int_{0}^{1} \mrm{Re} \left( e^{ixuT} K(u) \right) \varphi_{X}(uT) \mrm{d}{u}.
	\]
Hence, for $Z \sim N(0,1)$, and for any $T > 0$, $q \in [0,1]$, we have
	\begin{equation}\label{eq:prawitz_renew}
	\begin{aligned}
	\Pr[Z < x]- \Pr[X < x]
	\leq
	& \left(\Pr[Z < x] - \frac{1}{2} \right)
	+ \int_{0}^{1} 2\mrm{Re} \left( e^{iTux} K(u) \right) \varphi_{X}(uT) \mrm{d}{u} = \\
	=
	& \int_{0}^{q} 2\mrm{Re} \left( e^{iTux} K(u) \right) \left( \varphi_{X}(uT) - \varphi_{Z}(uT) \right) \mrm{d}{u} + \\
	& +\int_{q}^{1} 2\mrm{Re} \left( e^{iTux} K(u) \right) \varphi_{X}(uT) \mrm{d}{u} + \\
	& +\int_{0}^{q} 2 \mrm{Re} \left( e^{iTux} K(u) \right) \varphi_{Z}(uT) \mrm{d}{u} + \\
	& +\left( \Pr[Z < x] - \frac{1}{2} \right) \leq \\
	\leq
	(S_{1}=) & \int_{0}^{q} \left| 2\mrm{Re} \left( e^{iTux} K(u) \right) \right| \left| \varphi_{X}(uT) - \varphi_{Z}(uT) \right| \mrm{d}{u} + \\
	+(S_{2}=) & \int_{q}^{1} \left| 2\mrm{Re} \left( e^{iTux} K(u) \right) \right| \left| \varphi_{X}(uT) \right| \mrm{d}{u} + \\
	+(S_{3}=) & \int_{0}^{q} 2 \mrm{Re} \left( e^{iTux} K(u) \right) \varphi_{Z}(uT) \mrm{d}{u} + \\
	+(S_{4}=) & \left( \Pr[Z < x] - \frac{1}{2} \right).
	\end{aligned}
	\end{equation}
	Notice that given $x,T,$ and $q$, the quantities $S_{3}, S_{4}$ are two constants which are, in principle, easy to compute, as $\varphi_{Z}(v)=\exp(-v^2/2)$. In the following, we obtain bounds on $S_{1}$ and $S_{2}$, and deduce Proposition~\ref{prop:Prawitz-Rademacher}.
	
	\paragraph{Bounding $\left| \varphi_{X}(uT) \right|$.} We claim that
	\begin{equation}\label{eq:be_fx}
	\left| \varphi_{X}(v) \right| \leq
	\begin{cases}
	\exp(-v^{2}/2),					& 0\leq a_1 v \leq \theta\\
	(-\cos(a_1 v))^{1/a_1^2},	    & \theta \leq a_1 v \leq \pi\\
	1,								& \mrm{Otherwise}
	\end{cases},
	\end{equation}
	where $\theta$ is the unique root of
	\[
	\exp(-x^2/2)+\cos(x)=0
	\]
	in the interval $[0,\pi]$. Its numerical value is $1.778\pm 10^{-4}$.
	
	\medskip \noindent
	To see this, recall that $\varphi_{X}(v) = \prod_{i} \cos(a_i v)$. Clearly, $|\varphi_{X}(v)| \leq 1$. Moreover, it is easy to check by differentiation that as long as $a_i v \leq \theta$, we have $|\cos(a_i v)| \leq \exp(-(a_i v)^2/2)$. As $a_1=\max_i a_i$, it follows that if $a_1 v \leq \theta$, then
	\begin{equation}\label{eq:aux-prawitz}
	|\varphi_{X}(v)| = |\prod_{i} \cos(a_i v)| \leq \exp(-\sum_i a_i^2 v^2 / 2) = \exp(-v^2/2).
	\end{equation}
	To handle the remaining case, $a_1 v \in (\theta, \pi]$, note that
	\begin{equation}\label{Eq:Aux-Prawitz2}
		|\varphi_X(v)| = \exp\left( \sum_i \log|\cos(a_i v)| \right) = \exp\left( \sum_i a_i^2 \frac{\log|\cos(a_i v)|}{a_i^2} \right)
		\leq \exp\left( \max_i \frac{\log|\cos(a_i v)|}{a_i^2} \right),
	\end{equation}
	where the ultimate inequality holds since $\sum a_i^2 = 1$. The right hand side is maximized at $i=1$. Indeed,
	\begin{itemize}
		\item For $i$ with $a_i v \leq \theta$, by the previous case we have $\log|\cos(a_i v)|/a_i^2 \leq -v^2/2$.
		
		\item For $i$ with $a_i v \in  [\theta, \pi]$, as the function $\psi: a \mapsto \log|\cos(a)|/a^2$ increases in the range $a \in [\theta, \pi]$, we get $\psi(a_i v) \leq \psi(a_1 v)$.
	\end{itemize}
	Since $a_1=\max_i a_i$ satisfies $a_1 v \in (\theta, \pi]$, a combination of the two cases gives
	\[
	\forall i: \qquad \log|\cos(a_i v)|/a_i^2 \leq \max(-v^2/2, \log|\cos(a_1 v)|/a_1^2) = \log|\cos(a_1 v)|/a_1^2,
	\]
	yielding $\varphi_X(v) \leq |\cos(a_1 v)|^{1/a_1^2}$, as we claimed.
	
	\paragraph{Bounding $\left| \varphi_{X}(uT) - \varphi_{Z}(uT) \right|$.} We claim that
	\begin{equation}\label{eq:be_fxfz}
	\left| \varphi_{X}(v) - \varphi_{Z}(v) \right| \leq
	\begin{cases}
	\exp(-v^{2}/2) - \cos(a_1 v) ^ {1/a_1^2}, & 0\leq a_1 v \leq \frac{\pi}{2}\\
	\exp(-v^{2}/2)+1, & \mrm{Otherwise}
	\end{cases}.
	\end{equation}
	To see this, recall that $\varphi_{Z}(v) = \exp(-v^2/2)$, and hence, for any $v \in \mathbb{R}$,
	\[
	\left| \varphi_{X}(v) - \varphi_{Z}(v) \right| \leq \exp(-v^2/2)+1.
	\]
	In the case $0 \leq a_1 v \leq \pi / 2$, on the one hand, similarly to~\eqref{eq:aux-prawitz},
	\[
	\varphi_X(v) = \prod_i \cos(a_i v) \leq \exp(-\sum_i a_i^2 v^2/2) = \exp(-v^2/2)=\varphi_Z(v).
	\]
	On the other hand, by virtue of~\eqref{Eq:Aux-Prawitz2} and $\cos(a_i v) \geq 0$,
	\[
	\prod_i \cos(a_i v) \geq \exp(\min_i (\log(\cos(a_i v)) / a_i^2)).
	\]
	As the function $a \mapsto \log(\cos(a))/a^2$ decreases in the range $a \in (0, \pi/2)$, one has that for all $i$, $\log(\cos(a_i v)) / a_i^2 \geq \log(\cos(a_1 v)) / a_1^2$, and thus, \[
	\varphi_Z(v) \geq \varphi_X(v)=\prod_i \cos(a_i v) \geq \exp(\min_i (\log(\cos(a_i v)) / a_i^2)) = \cos(a_1 v)^{1/a_1^2},
	\]
	yielding~\eqref{eq:be_fxfz}.
	
	\paragraph{Simplifying $2\mrm{Re} \left( e^{iTux} K(u) \right)$.}
	We claim that for all $u \in (0,1)$,
	\begin{equation}\label{eq:k_def}
		k(u,x,T) \mathrel{\mathop:}= 2\mrm{Re} \left( e^{iTux} K(u) \right) = \frac{(1-u)\sin(\pi u - T u x)}{\sin(\pi u)} - \frac{\sin(T u x)}{\pi}.
	\end{equation}
	To verify~\eqref{eq:k_def}, notice that by definition, $K(u) = \frac{1-|u|}{2} + \frac{i}{2} \left( (1-|u|) \cot(\pi u) + \frac{\mrm{sgn}(u)}{\pi} \right)$ and $\exp(iTux) = \cos(Tux)+i\sin(Tux)$, and thus, for $u \in (0,1)$ we have
	\[
		k(u,x,T) = \frac{2\cos(Tux)}{2}(1-u) - \frac{2\sin(Tux)}{2}((1-u)\cot(\pi u)+1/\pi).
	\]
	Substituting $\cot(\pi u) = \cos(\pi u) / \sin(\pi u)$, we get
	\[
		k(u,x,T) = (1-u)\left(\cos(Tux) - \frac{\sin(Tux)\cos(\pi u)}{\sin(\pi u)}\right) - \sin(Tux)/\pi.
	\]
	Using the identity $\sin(\alpha-\beta)=\sin(\alpha)\cos(\beta)-\sin(\beta)\cos(\alpha)$, we derive~\eqref{eq:k_def}.
	
	\paragraph{Combining the bounds.} Substituting the bounds~\eqref{eq:be_fx} and~\eqref{eq:be_fxfz} and the simplification~\eqref{eq:k_def} into~\eqref{eq:prawitz_renew}, we obtain~\eqref{Eq:Our-Prawitz}, namely, the assertion of Proposition~\ref{prop:Prawitz-Rademacher}.
	
	
	\subsection{Applications of the refined Berry-Esseen type inequalities}
	\label{sec:sub:BE-applications}
	
	\subsubsection{Tomaszewski's conjecture for \tops{$a_1 \leq 0.31$}}
	
	We prove Proposition~\ref{lem:be_toma}, which implies Tomaszewski's conjecture in the range $a_1 \leq 0.31$. 		
	\begin{proof}[Proof of Proposition~\ref{lem:be_toma}]
		Consider first the case $a_1=0.31$. Applying Proposition~\ref{prop:Prawitz-Rademacher} with $a_1=0.31$, $x=1$, $T=10$ and $q=0.4$, we obtain
		\begin{equation}\label{eq:0.31}
			\Pr[Z < 1] - \Pr[X < 1] \leq 0.09114 \pm 10^{-5} \leq 0.09115.
		\end{equation}
		Consequently, $\Pr[X < 1] \geq \Pr[Z < 1] - 0.09115 > 0.7501$, and since $X$ is a symmetric random variable,
		\[
		\Pr[|X| < 1] = 2\Pr[X < 1] - 1 \geq 0.5002,
		\]
		as asserted.
		
		To handle the case $a_1 < 0.31$, note that the bound in the right hand side of~\eqref{Eq:Our-Prawitz} is increasing in $a_1$, and thus, an application of Proposition~\ref{prop:Prawitz-Rademacher} with $a_1<0.31$ and the same values $x,T,q$ as above, leads to a stronger lower bound on $\Pr[|X| < 1]$. This completes the proof.
	\end{proof}
	
	\subsubsection{A Berry-Esseen type inequality for Rademacher sums with \tops{$a_1 \leq 0.22$}}
	To prove Proposition~\ref{prop:ad-hoc2}, we use the following lemma, whose proof is given in Appendix~\ref{ssec:ad-hoc}.

	\begin{lemma}
		\label{lem:ad-hoc}
		Let $X = \sum_i a_i x_i$ be a Rademacher sum with $\max_i a_i \leq 0.22$ and $\var(X) = 1$. Then for every $x \geq 0.35$, we have
		\begin{equation}\label{eq:ad-hoc}
		\Pr[X \leq x] \geq \Pr[Z \leq x] - 0.084,
		\end{equation}
		where $Z \sim N(0,1)$ is a standard Gaussian variable.
	\end{lemma}
	The proof of Lemma~\ref{lem:ad-hoc} proceeds by applying Proposition~\ref{prop:Prawitz-Rademacher} to $X$, with suitably chosen parameters $T,q$, and obtaining a slightly stronger version of~\eqref{eq:ad-hoc} for a finite set of $x$'s. Choosing this set of $x$'s fine enough,~\eqref{eq:ad-hoc} follows for all $x \geq 0.35$, by the monotonicity of $x\mapsto \Pr[X \leq x]$.
	
	\medskip
	
	Proposition~\ref{prop:ad-hoc2} follows from Lemma~\ref{lem:ad-hoc} and Lemma~\ref{lem:seg-compare2}.
	
	\begin{proof}[Proof of Proposition~\ref{prop:ad-hoc2}]
		The proof is split according to the value of $x$.
		For $x \in [0, a_1)$ we have
		\[
		\Pr[X \leq x] \geq 1/2 \geq \Pr[Z \leq x] - \Pr[|Z| \leq a_1]/2,
		\]
		implying~\eqref{eq:ad-hoc2}. For $x \in [0, 0.2]$, we have $\Pr[Z \leq x] \leq 0.58$, and thus, $\Pr[X \leq x] \geq 1/2 \geq \Pr[Z \leq x] - 0.084$, as asserted. For $x \geq 0.35$, the assertion~\eqref{eq:ad-hoc2} follows directly from Lemma~\ref{lem:ad-hoc}.
		
		\medskip Hence, it is left to prove the assertion for $x \in [\max(a_1, 0.2), 0.35]$. We show that in this range, $\Pr[X \leq x] \geq \Pr[Z \leq x] - 0.084$.
		
		Indeed, applying Lemma~\ref{lem:seg-compare2} to $X$, with the parameters $A,B,C,D,M = -x, x, x+\epsilon, 2x+\epsilon/2, a_1$ and letting $\epsilon\to 0^{+}$, we obtain
		$
		\Pr[|X| \leq x] \geq \Pr[X \in (x, 2x]],
		$
		and thus,
		\[
		\Pr[X \in \langle 0,x ] ] \geq \frac{1}{3} \Pr[X \in \langle 0,2x] ].
		\]
		(Note that the parameters $A,B,C,D,M$ satisfy the assumptions of Lemma~\ref{lem:seg-compare2} since $x \geq a_1$.)
		Applying Lemma~\ref{lem:ad-hoc} with the parameter $2x$ (which can be done, as by assumption, $2x \geq 0.4> 0.35$), and using the symmetry of $X$, we get
		\[
		\Pr[X \leq x] \geq 1/2 + \frac{1}{3}\Pr[X \in \li\langle 0, 2x\right]] \geq \frac{1}{2} + \frac{1}{3}(\Pr[Z \leq 2x] - 0.584).
		\]
		Therefore, in order to complete the proof it is sufficient to show that
		\begin{equation}\label{eq:ad-aux}
		\frac{1}{2} + \frac{1}{3}(\Pr[Z \leq 2x] - 0.584) \geq \Pr[Z \leq x] - 0.084,
		\end{equation}
		The inequality~\eqref{eq:ad-aux} indeed holds for all $x \in [0.2, 0.35]$. To see this, note that the function $x \mapsto \Pr[Z \leq 2x] / 3 - \Pr[Z \leq x]$ is decreasing in $[0.2,0.35]$, and thus, it suffices to verify~\eqref{eq:ad-aux} for $x=0.35$. At $x=0.35$, the inequality holds, completing the proof.
	\end{proof}
	
	

\section{Theorem~\ref{thm:main} for \tops{$a_1 + a_2 \geq 1$}, via a Semi Inductive Argument}\label{sec:induction}

In this section we prove the following result.
\begin{proposition}\label{prop:semi-inductive}
	Let $3 \leq n \in \mathbb{N}$. Assume that for any Rademacher sum $Z=\sum_{i=1}^m a_i x_i$ with $m < n$ and $\var(Z)=1$, we have $\Pr[|Z|\leq 1] \geq 1/2$.
	
	Let $X=\sum_{i=1}^n a_i x_i$ be a Rademacher sum, such that $\var(X)=1$ and $a_1+a_2 \geq 1$. Then $\Pr[|X|\leq 1] \geq 1/2$.
\end{proposition}
There is no restriction in assuming $n \geq 3$, as the assertion of Theorem~\ref{thm:main} (namely, $\Pr[|X|\leq 1] \geq 1/2$) holds trivially for Rademacher sums with $n \leq 2$. Proposition~\ref{prop:semi-inductive} is only `semi-inductive' in the sense that it assumes that Theorem~\ref{thm:main} holds for all $m <n$, with no restriction on the $a_i$'s, and deduces Theorem~\ref{thm:main} for $m=n$ only in the case $a_1+a_2 \geq 1$. Hence, it can be used only if we resolve the case $a_1+a_2<1$ by a different argument, as we do in the following sections.

The proof relies on a `stopping time' argument that is reminiscent of the stopping time argument of Ben-Tal et al.~\cite{BNR02} used in all recent works on Tomaszewski's conjecture.

\paragraph{Elimination of two variables.} We start with the following variant of Lemma~\ref{lem:nm}.
\begin{lemma}\label{cor:nm2}
	Let $X = \sum_{i=1}^{n} a_{i} x_i = a_1 x_1 + a_2 x_2 + \sigma X'$ with $\var(X) = \var(X') = 1$ (so that $\sigma=\sqrt{1-a_1^2-a_2^2}$). The assertion
	\[
	\Pr[|X| \leq 1] \geq 1/2
	\]
	is equivalent to the following inequality involving $X'$:
	\begin{equation}\label{eq:gt1_ineq}
	\Pr\left[ X' \in [L_{1}, L_{2}] \right] \geq \Pr \left[ X' > R_{1} \right] + \Pr \left[ X' > R_{2} \right],
	\end{equation}
	where
	\[
	L_1, L_2 = \frac{a_1+a_2-1}{\sigma}, \frac{1-a_1+a_2}{\sigma},
	\]
	and
	\[
	R_1, R_2 = \frac{1+a_1-a_2}{\sigma}, \frac{1+a_1+a_2}{\sigma}.
	\]
\end{lemma}
\begin{proof}
	The assertion follows immediately from Lemma~\ref{lem:nm} with $m=2$, since  $\Pr[X' \in [L_1, L_2]] = 1 - \Pr[X' > -L_1] - \Pr[X' > L_2]$.
\end{proof}

\noindent Note that if $a_1 \geq a_2$ and $a_1+a_2 \geq 1$ then the parameters $L_1,L_2,R_1,R_2$ satisfy
\begin{equation}\label{Eq:Aux-Induction1}
0 \leq L_1 < L_2 \leq R_1 < R_2.
\end{equation}
This sequence of inequalities will be used several times in the sequel.

\paragraph{The semi-inductive stopping time argument}

Let $X = \sum_{i=1}^{n} a_i x_i$ (with $n \geq 3$) be a Rademacher sum with $\var(X)=1$, and write $X = a_1 x_1 + a_2 x_2 + \sigma X'$, as in Lemma~\ref{cor:nm2}. For $i \geq 3$, write $a_i' = a_i / \sigma$ so that $X' = \sum_{i=3}^{n} a_i' x_i$. By Lemma~\ref{cor:nm2}, in order to deduce $\Pr[|X|\leq 1]\geq 1/2$, it suffices to verify~\eqref{eq:gt1_ineq}.

Write $X'$ as the sum of two random variables $X'=Y'+Z'$, as follows. Let the random variable $k$ to be the minimal index with $\sum_{i=3}^{k} a_{i}'x_{i} \geq L_{1}$, and set
\[
Y' \mathrel{\mathop:}= \sum_{i=3}^{k} a_{i}'x_{i}, \qquad \mbox{and} \qquad Z' \mathrel{\mathop:}= \sum_{i=k+1}^n a_{i}' x_{i}.
\]
If no such index exists, let $k=n$ and set $Z'=0$.

\medskip By lemma~\ref{cor:nm2}, in order to prove $\Pr[|X| \leq 1] \geq 1/2$, it suffices to prove~\eqref{eq:gt1_ineq}, that is
\begin{equation}\label{eq:gt11}
\Pr\left[ Y'+Z' \in [L_{1}, L_{2}] \right] \geq \Pr \left[ Y'+Z' > R_{1} \right] + \Pr \left[ Y'+Z' > R_{2} \right].
\end{equation}
We shall show that~\eqref{eq:gt11} holds even if we condition on any possible value of $k,Y'$. This is clearly sufficient, due to the law of total probability.

For any specific assignment of $k$ and $Y'$, the above inequality is a probabilistic inequality involving the random variable $Z'$. We consider two cases:
\begin{itemize}
	\item \emph{Case~1: $Z' \equiv 0$.} We show that in this case,~\eqref{eq:gt11} holds as its right hand side is $0$.
	
	\item \emph{Case~2: $Z' \not \equiv 0$.} In this case, we show that~\eqref{eq:gt11} follows from the inequality~\eqref{eq:gt1_ineq} applied to the Rademacher sum $Z'/\sqrt{\var(Z')}$. To show that the latter inequality holds, we note that when $k$ is fixed, $Z'$ is a Rademacher sum on the $n-k$ variables $x_{k+1},\ldots,x_n$. Hence, by applying Lemma~\ref{cor:nm2} in the inverse direction, we may infer~\eqref{eq:gt1_ineq} for $Z'$ from the assertion $\Pr[|Z|\leq 1]\geq 1/2$ for an appropriate Rademacher sum $Z$ on $n-k+2$ variables, which holds due to the inductive hypothesis, since $k \geq 3$.
\end{itemize}

\noindent For the proof of~\eqref{eq:gt11}, we observe the following relation between $Y'$ and $\var(Z' | Y')$.
\begin{claim}
	\label{claim:aux-induction}
	Let $X',Y',Z'$ be as defined above, assume $Y' \geq L_1$ and let $s=(1-\sum_{i=3}^k (a'_i)^2)^{1/2}$. We have
	\begin{equation}\label{eq:gt1_sy}
	Y'(Y' - L_{1}) \leq 1 - s^2.
	\end{equation}
\end{claim}

\begin{proof}
By the definition of $k$, we have $Y'-L_{1} \leq a_{k}' \leq a_{k-1} \leq \ldots \leq a_3'$. Thus,
\[
1-s^{2} = \sum_{i=3}^{k} (a'_{i})^{2} \geq \min_{3 \leq i \leq k} \left\{ a_{i}'\right\} \sum_{i=3}^{k} a_{i}' \geq (Y'-L_{1})
\sum_{i=3}^{k} a'_{i} x_{i} = (Y'-L_{1}) Y',
\]
as asserted.
\end{proof}

\paragraph{The case $Z' \equiv 0$.} We observe that in this `singular' case, the right hand side of~\eqref{eq:gt11} is zero, and hence the inequality trivially holds.
Indeed, $Z' \equiv 0$ occurs in one of two cases:
\begin{itemize}
	\item There does not exist $k$ such that $Y' = \sum_{i=3}^{k} a_{i}'x_{i} \geq L_{1}$. In this case, $Y'+Z'=\sum_{i=3}^{n} a_{i}'x_{i} < L_1$, and thus, the right hand side of~\eqref{eq:gt11} is clearly equal to zero by~\eqref{Eq:Aux-Induction1}.
	
	\item The minimal $k$ such that $Y' \mathrel{\mathop:}= \sum_{i=3}^{k} a_{i}'x_{i} \geq L_{1}$ is $k=n$.
	By~\eqref{Eq:Aux-Induction1}, in order to show that the r.h.s. of~\eqref{eq:gt11} is equal to zero, it is sufficient to prove that $Y'=Y'+Z' < R_1$. To see this, observe that by Claim~\ref{claim:aux-induction}, $Y'(Y'-L_1) \leq 1$, and hence $Y' < R_1$ follows from $R_1(R_1 - L_1) > 1$ (recall $0 \leq L_1 \leq R_1$ by~\eqref{Eq:Aux-Induction1}). This latter inequality reads as $2(1+a_1-a_2)(1-a_2)/\sigma^2 > 1$, where $\sigma^2=1-a_1^2-a_2^2$ and $a_1 \geq a_2$, and follows by
	\[
		2(1+a_1-a_2)(1-a_2)=\sigma^2+(a_1-a_2)(2+a_1-a_2)+(2a_2-1)^2/2+1/2 > \sigma^2.
	\]
\end{itemize}


\paragraph{The case $Z' \not \equiv 0$.} Denote $s = (\var(Z'))^{1/2} = (\sum_{i=k+1}^n (a'_i)^2)^{1/2}$, so that $\frac{1}{s} Z'$ is a Rademacher sum with variance~1 on $n-k$ variables. We have to prove~\eqref{eq:gt11} which reads as
\begin{equation}\label{eq:gt1_need}
\Pr\left[ \frac{Z'}{s} \in \left[ \frac{L_{1}-Y'}{s}, \frac{L_{2}-Y'}{s}\right] \right] \geq \Pr \left[ \frac{Z'}{s} > \frac{R_{1}-Y'}{s} \right] + \Pr \left[ \frac{Z'}{s} > \frac{R_{2}-Y'}{s} \right].
\end{equation}
(Note that we assume $k,Y'$ are fixed, and hence, the probabilities in~\eqref{eq:gt1_need} depend only on $Z'$.)
We would like to deduce~\eqref{eq:gt1_need} from the assertion $\Pr[|Z|\leq 1]\geq 1/2$ for an auxiliary Rademacher sum $Z$ on $n-k+2$ variables, which holds due to the inductive hypothesis (since $n-k+2<n$).

\medskip To this end, we pick $b_1, b_2 \in \mathbb{R}$ such that
\begin{equation}\label{Eq:Aux-Induction3}
\frac{L_{1}-Y'}{s}, \frac{L_{2}-Y'}{s} =\mathrel{\mathop:} L_{1}', L_{2}' = \frac{b_1+b_2-1}{\sigma'}, \frac{1-b_1+b_2}{\sigma'},
\end{equation}
where $\sigma' = \sqrt{1-b_1^2 -b_2^{2}}$. (Concrete values of the possibly negative $b_1, b_2$ are given below.) We define a Rademacher sum $Z = b_1 z_1 + b_2 z_2 + \frac{\sigma'}{s} Z'$, let
\[
R_{1}', R_{2}' = \frac{1+b_1-b_2}{\sigma'}, \frac{1+b_1+b_2}{\sigma'},
\]
and show that $R'_1$ and $R'_2$ satisfy
\begin{equation}\label{eq:gt1_RR}
R_{1}' \leq \frac{R_{1}-Y'}{s} \qquad \mbox{and} \qquad R_{2}' \leq \frac{R_{2}-Y'}{s}.
\end{equation}
As $Z$ is a Rademacher sum with variance~1 on $n-k+2<n$ variables, the induction hypothesis together with Lemma~\ref{cor:nm2} yields
\[
\Pr\left[\frac{Z'}{s} \in [L'_{1}, L'_{2}] \right] \geq \Pr \left[\frac{Z'}{s} > R'_{1} \right] + \Pr \left[\frac{Z'}{s} > R'_{2} \right],
\]
which implies~\eqref{eq:gt1_need} via~\eqref{eq:gt1_RR}. So, it is only left to show that $Z$ is well defined and that~\eqref{eq:gt1_RR} holds.

\paragraph{Why is $Z$ well-defined?}

To show that there exist $b_1,b_2 \in \mathbb{R}$ that satisfy~\eqref{Eq:Aux-Induction3}, let
\[
b_1 = \frac{2 + 2L_1' L_2'}{2 + (L'_1)^2 + (L'_2)^2} \qquad  \mbox{and} \qquad b_2 = \frac{(L'_2)^2 - (L'_1)^2}{2 + (L'_1)^2 + (L'_2)^2}.
\]
A direct computation shows that
\begin{equation}\label{Eq:Aux-Induction4}
\sigma' = \sqrt{1-b_1^2-b_2^2} = \frac{2(L'_2-L'_1)}{2+(L'_1)^2+(L'_2)^2},
\end{equation}
and in particular, $b_1^2+b_2^2 < 1$ (via~\eqref{Eq:Aux-Induction1} and the definition of $L_1', L_2'$ in~\eqref{Eq:Aux-Induction3}).
A further direct computation shows that the right equality in~\eqref{Eq:Aux-Induction3} holds as well.

\paragraph{Proving~\eqref{eq:gt1_RR}.}
To verify the two inequalities in~\eqref{eq:gt1_RR}, notice that by adding $L_{2}'$ to both sides of the first, and $-L_1'$ to both sides of the second, and recalling the definitions of $L_1,L_2,R_1,R_2$ and $L_1', L_2', R_1', R_2'$, these inequalities are respectively equivalent to:
\[
\frac{s}{\sigma'} + Y' \leq \frac{1}{\sigma} \qquad \mbox{and} \qquad \frac{s}{\sigma'} \leq \frac{1}{\sigma}.
\]
As $Y' \geq L_1 \geq 0$ by~\eqref{Eq:Aux-Induction1}, the former inequality clearly implies the latter; hence, we focus only on it. Note that similarly to~\eqref{Eq:Aux-Induction4}, we have
\[
\sigma = \frac{2(L_2-L_1)}{2 + L_1^2 + L_2^2}.
\]
In addition, by~\eqref{Eq:Aux-Induction3}, we have $L'_2-L'_1 = (L_2-L_1)/s$. Using this and substituting the values of $\sigma,\sigma'$, the inequality we seek to prove $\frac{s}{\sigma'} + Y' \leq \frac{1}{\sigma}$, reads as
\[
\frac{s^{2}(2+L_1'^2+L_2'^2)}{2(L_2-L_1)} + Y' \leq \frac{(2+L_1^2+L_2^2)}{2(L_2-L_1)}.
\]
Multiplying by $2(L_2-L_1)$ and substituting the values of $L_1', L_2'$ from~\eqref{Eq:Aux-Induction3}, we reduce to showing
\[
2s^2 + (L_1-Y')^2 + (L_2-Y')^2 + 2Y'(L_2-L_1) \leq 2 + L_1^2 + L_2^2,
\]
Since $s^2 \leq 1-Y'(Y' - L_{1})$ by Claim~\ref{claim:aux-induction}, it is sufficient to prove that
\[
2 - 2Y'(Y'-L_1) + (L_1-Y')^2 + (L_2-Y')^2 + 2Y'(L_2-L_1) \leq 2+L_1^2+L_2^2.
\]
Simplifying this inequality, one sees it is equivalent to the inequality $2Y' \cdot L_{1} \geq 0$, which indeed holds since by~\eqref{Eq:Aux-Induction1}, we have $0 \leq L_{1} \leq Y'$. This completes the proof of Proposition~\ref{prop:semi-inductive}.



\section{Theorem~\ref{thm:main} for \tops{$a_1 \geq 0.55$}, \tops{$a_1+a_2 < 1$}}\label{sec:055}
	In the previous sections we handled Theorem~\ref{thm:main} in the cases $a_1 \leq 0.31$ (Section~\ref{sec:sub:BE-applications}), and $a_1+a_2 \geq 1$ (Section~\ref{sec:induction}, semi-inductively). In this section we handle the case $(a_1 \geq 0.55) \wedge (a_1 + a_2 < 1)$.

	

	
	\paragraph{Elimination step.} Let $X = \sum_{i=1}^{n} a_i x_i$ be a Rademacher sum with $\var(X)=1$, $a_1 \geq (1+\sqrt{8})/7$, and $a_1+a_2 < 1$. (Note that $1+\sqrt{8}/7 \leq 0.55$.)
	We want to prove $\Pr[|X| \leq 1] \geq 1/2$.
	
	\medskip By the case $m=1$ of Lemma~\ref{lem:nm}, it is sufficient to prove that
	\begin{equation}\label{Eq:Aux6.1}
	\Pr[X' \in \li\langle 0, t\right] ] \geq \Pr[X' > 1/t],
	\end{equation}
	where
	\[
	\sigma = \sqrt{1-a_1^2}, \qquad a'_i = \frac{a_i}{\sigma}, \qquad X'=\sum_{i=2}^n a'_i x_i, \qquad \mbox{and} \qquad t=\sqrt{\frac{1-a_1}{1+a_1}}=\frac{1-a_1}{\sigma}
	\]
	(see~\eqref{eq:nm1} and~\eqref{Eq:Prelim-Eliminate-one} above). As we assume $a_1 + a_2 < 1$, we have
	\begin{equation}\label{Eq:Aux6.2}
	\forall i\colon a_i' < t.
	\end{equation}
	
	\paragraph{Segment comparison step.}
	
	\begin{claim}\label{Cl:Aux6.1}
		Let $X',t$ be as defined above. Then:
		\begin{enumerate}
			\item[(a)] $\hpr{X'}{t}{2t} \leq 2\hpr{X'}{0}{t},$ and
			
			\item[(b)] $\forall k \geq 2 \colon \hpr{X'}{kt}{(k+1)t} \leq 4\hpr{X'}{0}{t}$.
		\end{enumerate}
	\end{claim}
	
	\begin{proof}$\phantom{}$

\noindent	(a) Applying Lemma~\ref{lem:seg-compare2} to $X'$, with the parameters $A,B,C,D,M=-t,t,t,2t,a_2'$, we get
		\[
		\hpr{X'}{t}{2t} \leq \hpr{X'}{-t}{t}.
		\]
		(Note that $2M\leq C-A$ follows from~\eqref{Eq:Aux6.2}). By the symmetry of $X'$, this implies~(a).
	
\medskip \noindent
		(b) Applying Lemma~\ref{lem:seg-compare1} to $X'$, with the parameters $A,B,C,D,M=-t, 2t, kt, (k+1)t, a_2'$, we get $\hpr{X'}{kt}{(k+1)t} \leq \hpr{X'}{-t}{2t}$. Using (a) as
		\[
		\hpr{X'}{-t}{2t} = \hpr{X'}{-t}{t} + \hpr{X'}{t}{2t} \leq 4 \hpr{X'}{0}{t},
		\]
		the assertion (b) follows.
	\end{proof}
	
\paragraph{Chebyshev-type inequality step.} Applying the inequality~\eqref{eq:cheby_our} to $X'$, with
	\[
		c_0, c_1, c_2, c_3, \ldots, c_{\lceil 1/t \rceil} = 0, t, 2t, 3t, \ldots, 1 \qquad \mbox{and} \qquad d_0, d_1 = 1, 1/t,
	\]
	we obtain
	\[
	\sum_{k=0}^{\lceil 1/t \rceil-1} (1-(k t)^2) \hpr{X'}{k t}{(k+1)t} \geq \Big(\frac{1}{t^2}-1 \Big) \Pr[X' \geq 1/t].
	\]
	By Claim~\ref{Cl:Aux6.1}, this implies
	\[
		\Big( 1 + 2(1-t^2) + 4\sum_{k=2}^{\lceil 1/t \rceil -1} \left( 1-(kt)^2\right) \Big) \hpr{X'}{0}{t}
		\geq
		\Big( \frac{1}{t^2} - 1 \Big) \Pr[X' \geq 1/t].
	\]
	Dividing both sides by $1/t^2-1$, we obtain an inequality of the form
	\[
	C_{t} \cdot \hpr{X'}{0}{t} \geq \Pr[X' \geq 1/t].
	\]
	This inequality implies~\eqref{Eq:Aux6.1}, provided  $C_{t} \leq 1$. Hence, it is left to verify:
	\begin{equation}\label{eq:055fin}
		C_{t} \stackrel{?}{\leq} 1, \quad \text{with} \quad C_{t} = \frac{1 + 2(1-t^2) + 4\sum_{k=2}^{\lceil 1/t \rceil-1} \left( 1-(kt)^2\right)}{(1/t^2) - 1}, \quad 0 < t \leq \sqrt{1-2^{-1/2}}.
	\end{equation}
	(Note that the condition $0< t \leq (1-2^{-1/2})^{1/2}$ follows from the assumption $a_1 \in \left[ (1+\sqrt{8})/7, 1\right)$, via $t=\sqrt{(1-a_1)/(1+a_1)}$. This is the only place where the assumption $a_1 \geq 0.55$ is used.) The derivation of~\eqref{eq:055fin} is presented in Appendix~\ref{app:055fin}.


\section{Theorem~\ref{thm:main} for \tops{$0.5 \leq a_1 \leq 0.55$}, \tops{$a_1 + a_2 < 1$}}\label{sec:0.5<a_1<0.55}
	The proof of Theorem~\ref{thm:main} in this range is split into two cases: Small $a_2$ and large $a_2$. The threshold between the cases depends on $a_1$, being  $(a_1-3+\sqrt{25+10a_1-63a_1^2})/8$.
	
	\subsection{The case \tops{$a_2 \leq (a_1-3+\sqrt{25+10a_1-63a_1^2})/8$}}
	
	Let $X = \sum a_i x_i$ be a Rademacher sum with $\var(X)=1$, $a_1 \in [0.5, 0.55]$, $a_1+a_2 < 1$, and $a_2 \leq (a_1-3+\sqrt{25+10a_1-63a_1^2})/8$. The proof that $\Pr[|X| \leq 1] \geq 1/2$ is almost identical to the argument of Section~\ref{sec:055}, as we explain below.
	
	\paragraph{Elimination step.} Like in Section~\ref{sec:055}, we note that it is sufficient to prove $\Pr[X' \in \li\langle 0, t\right] ] \geq \Pr[X' > 1/t]$, where $X',t$ are defined as in~\eqref{Eq:Aux6.1}.
	
	\paragraph{Segment comparison step.} Instead of Claim~\ref{Cl:Aux6.1}, we use the following comparisons:	
	\begin{equation}\label{eq:05rep}
	\hpr{X'}{t}{3t/2} \leq \hpr{X'}{0}{t} \quad \mbox{and} \quad \hpr{X'}{3t/2}{1} \leq \hpr{X'}{0}{t}.
	\end{equation}
	The first inequality follows from Lemma~\ref{lem:seg-compare2}, applied to $X'$ with the parameters $A,B,C,D,M = 0, t, t, 3t/2, a_2/\sigma$, and the second inequality follows from Lemma~\ref{lem:seg-compare1}, applied to $X'$ with the parameters $A,B,C,D,M = 0, t, 3t/2, 1, a_2/\sigma$. To show that Lemmas~\ref{lem:seg-compare2} and~\ref{lem:seg-compare1} indeed can be applied (i.e., that the assumptions of the lemmas are satisfied), it is sufficient to verify:
	\begin{equation}\label{eq:05saux}
	\begin{gathered}
	\frac{2a_2}{\sigma} \stackrel{?}{\leq} t, \qquad \quad (1 - 3t/2) + \frac{2a_2}{\sigma} \stackrel{?}{\leq} t\\
	\text{with:}\qquad a_1 \in [0.5, 0.55],\quad\sigma = \sqrt{1-a_1^2},\quad\\ t=\sqrt{\frac{1-a_1}{1+a_1}},\quad a_2 \leq \frac{a_1-3+\sqrt{25+10a_1-63a_1^2}}{8}.
	\end{gathered}
	\end{equation}
	These inequalities are proved in Appendix~\ref{app:05saux}.
	
	\paragraph{Chebyshev-type inequality step.} Note that as $a_1 \geq 1/2$, we have $t=\sqrt{(1-a_1)/(1+a_1)} \leq 1/\sqrt{3}< 2/3$.
	Applying the inequality~\eqref{eq:cheby_our} to $X'$, with
	\[
	c_0, c_1, c_2, c_3 = 0, t, 3t/2, 1 \qquad \mbox{and} \qquad d_0, d_1 = 1, 1/t,
	\]
	and using~\eqref{eq:05rep}, we obtain
	\[
	(1 + (1-t^2) + (1-(3t/2)^2)) \hpr{X'}{0}{t} \geq \left(\frac{1}{t^2}-1\right) \Pr[X' \geq 1/t].
	\]	
	Hence, the task of deducing~\eqref{Eq:Aux6.1} boils down to verifying:
	\begin{equation}\label{eq:05rep2}
	C_t' \stackrel{?}{\leq} 1, \qquad \text{with:}\qquad C_t' = \frac{1 + (1-t^2) + (1-(3t/2)^2)}{(1/t^2)-1},\quad t^2 \in (0, 1/3].
	\end{equation}
	This verification is done in Appendix~\ref{app:05fin2}.
	
	\subsection{The case \tops{$a_2 \geq (a_1-3+\sqrt{25+10a_1-63a_1^2})/8$}}
	
	Let $X = \sum a_i x_i$ be a Rademacher sum with $\var(X)=1$, $a_1 \in [0.5, 0.55]$, $a_1+a_2 < 1$, and $a_2 \geq (a_1-3+\sqrt{25+10a_1-63a_1^2})/8$. The proof of $\Pr[|X| \leq 1] \geq 1/2$ is similar to the above strategy, but this time, two variables are eliminated.
	
	\paragraph{Elimination step.} By Lemma~\ref{cor:nm2}, it it sufficient to show that
	\begin{equation}\label{eq:05need}
		\hpr{X'}{0}{-L_1} + \hpr{X'}{0}{L_2} \geq \Pr[X' > R_1] + \Pr[X' > R_2],
	\end{equation}
	where $X', \sigma, L_1, L_2, R_1, R_2$ are as defined in Lemma~\ref{cor:nm2}. (But this time, since $a_1+a_2<1$ we have $L_1<0$). Note that unlike the previous subsection, $X'$ depends on $n-2$ variables.
	
	\paragraph{Auxiliary estimates.} We use several auxiliary estimates on $L_2,R_1,R_2$:
	\begin{equation}\label{eq:05fin}
	\begin{gathered}
	L_2 \stackrel{?}{\geq} \frac{2}{3}, \qquad R_1 \stackrel{?}{\geq} \max(\sqrt{3 - L_2^2},\sqrt{2}), \qquad R_2 \stackrel{?}{\geq} \max(\sqrt{5 - 2L_2^2},\sqrt{3}),\\
	\text{with:}\qquad L_2 = \frac{1-a_1+a_2}{\sigma},\quad R_1 = \frac{1+a_1-a_2}{\sigma},\quad R_2 = \frac{1+a_1+a_2}{\sigma}, \\
	\sigma = \sqrt{1-a_1^2-a_2^2},\quad
	a_1 \in [0.5, 0.55],\quad
	a_1+a_2 < 1,\\
	a_2 \geq \left( a_1-3+\sqrt{25+10a_1-63a_1^2}\right)/8.
	\end{gathered}
	\end{equation}
	These inequalities are proved in Appendix~\ref{app:05fin}.
	
	\paragraph{The sub-case $L_2 \geq 1$.} Applying the Chebyshev-type inequality~\eqref{eq:cheby_our} to $X'$, with $c_0,c_1=0,1$ and $d_1,d_2,d_3=1,\sqrt{2},\sqrt{3}$, we obtain
	\[
	\hpr{X'}{0}{1} \geq \Pr[X' \geq \sqrt{2}] + \Pr[X' \geq \sqrt{3}],
	\]
	which implies~\eqref{eq:05need} via~\eqref{eq:05fin}.
	
	\paragraph{The sub-case $L_2 < 1$.} Applying Lemma~\ref{lem:seg-compare2} to $X'$, with the parameters $A,B,C,D,M = 0, L_2, L_2, 1, a_{3}/\sigma$, we obtain
	\begin{equation}\label{Eq:Aux7.1}
	\hpr{X'}{L_2}{1} \leq \hpr{X'}{0}{L_2}.
	\end{equation}
	Notice that the assumptions of Lemma~\ref{lem:seg-compare2} are satisfied, as $2(D-B)=2(1-L_2)\leq L_2=C-A$ by~\eqref{eq:05fin}, and
	\[
	2M \leq \frac{2a_2}{\sigma} < \frac{1-a_1+a_2}{\sigma} = L_2 =C-A,
	\]
	by the assumption $a_1+a_2 < 1$.
	
	\medskip Applying the Chebyshev-type inequality~\eqref{eq:cheby_our} to $X'$, with $c_0,c_1,c_2=0,L_2,1$ and $d_1,d_2,d_3=1,\sqrt{3-L_2^2},\sqrt{5-2L_2^2}$, we obtain
	\begin{equation}\label{eq:05cheby}
	\begin{split}
		\hpr{X'}{0}{L_2} &+ (1-L_2^2)\hpr{X'}{L_2}{1} \geq \\
		&\geq (2-L_2^2)\Pr\left[X'\geq \sqrt{3-L_2^{2}}\right] + (2-L_2^2)\Pr\left[X' \geq \sqrt{5-2L_2^{2}}\right].
	\end{split}
	\end{equation}
	By~\eqref{Eq:Aux7.1}, this implies
	\[
	\hpr{X'}{0}{L_2} \geq \Pr\left[X'\geq \sqrt{3-L_2^{2}}\right] + \Pr\left[X' \geq \sqrt{5-2L_2^{2}}\right],
	\]
	which, in turn, implies~\eqref{eq:05need} via~\eqref{eq:05fin}. This completes the proof.

\section{The remaining case: $a_1 \in (0.31, 0.5)$}\label{sec:remaining}

Our proof is most involved in this range, although there are no remarkable tightness examples with $a_1 \in (0.31, 0.5)$ (except for $X = \frac{1}{3} \sum_{i=1}^9 x_i$, being the `lightest' appearing in Section~\ref{ssec:hard-cases}).


The full proof in this range is deferred to appendices~\ref{sec:31big},~\ref{sec:39geq}, and~\ref{sec:0.31<a_1<0.387}, corresponding to three main subcases. The general structure of the proof is to condition on the values of a few largest weights (say, $a_1, a_2, a_3$), usually through elimination (Lemma~\ref{lem:nm}), and to prove Tomaszewski's assertion~\eqref{eq:main} regardless of the values we condition on.
While the careful proof is somewhat cumbersome, it was plotted by considering several specific fixings of the large weights (say, $a_1,a_2,a_3 = 0.4, 0.3, 0.2$) and proving the assertion~\eqref{eq:main} under these fixings. Then, the proof was generalized to capture any such fixing.

We demonstrate the proof by presenting several (not fully) representative such fixings, and proving~\eqref{eq:main} under them.

\subsection{Subcase $a_1 + a_2 + a_3 \leq 1$}\label{ssec:rem-case1}
The following example concisely demonstrates all the steps in the proof of this case (given in Appendix~\ref{sec:31big}).

Assume
\[
	a_1, a_2, a_3 = 0.36, 0.2, 0.15,
\]
so that 3-elimination (Lemma~\ref{lem:nm}) reduces us to proving the following inequality for all Rademacher sums $X'$ with $\var(X')=1$, whose largest weight is $\leq 0.15/(1-0.36^2-0.2^2-0.15^2)^{1/2} < 0.17$:
\begin{equation}\label{eq:demo1}
\begin{gathered}
	\hpr{X'}{0}{0.32} + \hpr{X'}{0}{0.65} + \hpr{X'}{0}{0.76} + \hpr{X'}{0}{1.1}
	\\ \geq \\
	\Pr[X' > 1.12] + \Pr[X' > 1.45] + \Pr[X' > 1.56] + \Pr[X' > 1.9]
\end{gathered}
\end{equation}
Using Chebyshev's inequality~\eqref{eq:cheby_our}, we lower bound an expression similar to the LHS of~\eqref{eq:demo1}:
\begin{equation}\label{eq:demo1-cheby}
\begin{gathered}
	\hpr{X'}{0}{0.32} + 0.9\hpr{X'}{0.32}{0.65} +\\
	0.6\hpr{X'}{0.65}{0.76} + 0.5\hpr{X'}{0.76}{1}
	\\ \geq \\
	(0.25\Pr[X' > 1.12] + 0.25\Pr[X' > 1.23]) + 0.5\Pr[X' > 1.42] +\\
	(0.4\Pr[X' > 1.56]  + 0.1\Pr[X' > 1.6]) + 0.5\Pr[X' > 1.75].
\end{gathered}
\end{equation}
Can we deduce~\eqref{eq:demo1} from~\eqref{eq:demo1-cheby}? Not immediately. If we multiply~\eqref{eq:demo1-cheby} by $2$ and see what is `missing' in order to deduce~\eqref{eq:demo1}, we get an inequality weaker than:
\[
	\hpr{X'}{0}{0.32} + \hpr{X'}{0}{0.65} \geq 0.5\hpr{X'}{1.12}{1.23} + 0.2\hpr{X'}{1.56}{1.6}.
\]
Recall that the largest weight of $X'$ is at most $0.17$, so using segment comparison (specifically, Lemma~\ref{lem:seg-compare1}), we can prove this inequality by showing $\hpr{X'}{1.12}{1.23} \leq \hpr{X'}{0}{0.65}$ and $\hpr{X'}{1.56}{1.6} \leq \hpr{X'}{0}{0.65}$.


\subsection{Subcase $a_1 + a_2 + a_3 \geq 1$ and $a_1 \in (0.387, 0.5)$}\label{ssec:rem-case2}
The proof in this range is similar to that of Section~\ref{ssec:rem-case1}, but the details are much simpler. We again give a demonstration that captures the essence of the proof (given in Appendix~\ref{sec:39geq}).

Assume
\[
	a_1, a_2, a_3 = 0.4, 0.35, 0.3,
\]
so that 3-elimination (Lemma~\ref{lem:nm}) reduces us to prove the following inequality for all Rademacher sums $X'$ with $\var(X')=1$, whose largest weight is $\leq 0.3/(1-0.4^2-0.35^2-0.3^2)^{1/2} < 0.38$:
\begin{equation}\label{eq:demo2}
\begin{gathered}
	\hpr{X'}{0.07}{0.69} + \hpr{X'}{0}{0.82} + \hpr{X'}{0}{0.94}
	\\ \geq \\
	\Pr[X' > 1.57] + \Pr[X' > 1.7] + \Pr[X' > 1.83] + \Pr[X' > 2.58]
\end{gathered}
\end{equation}
We prove~\eqref{eq:demo2} even without the $\hpr{X'}{0.07}{0.69}$ term. Using Chebyshev's inequality~\eqref{eq:cheby_our}:
\begin{equation}\label{eq:demo2-cheby}
\begin{gathered}
	\hpr{X'}{0}{0.82} + 0.33\hpr{X'}{0.82}{0.94} + 0.12\hpr{X'}{0.94}{1}
	\\ \geq \\
	0.7 \Pr[X' > 1.31] + 0.7 \Pr[X' > 1.55] + 0.7 \Pr[X' > 1.77] + 0.7 \Pr[X' > 1.95].
\end{gathered}
\end{equation}
Can we deduce~\eqref{eq:demo2} from~\eqref{eq:demo2-cheby}? Not immediately. If try to deduce~$0.7\cdot$\eqref{eq:demo2} from~\eqref{eq:demo2-cheby} we see that what is `missing', is weaker than:
\[
	0.4\hpr{X'}{0}{0.82}-0.12\hpr{X'}{0.94}{1} \geq 0.
\]
Using segment comparison, and specifically Lemma~\ref{lem:seg-compare1}, barely applicable since $(1-0.94) + 2\cdot 0.38 = 0.82$, we conclude $\hpr{X'}{0.94}{1} \leq \hpr{X'}{0}{0.82}$. Also, we are equally satisfied with
\[
	\hpr{X'}{0.94}{1} \leq \hpr{X'}{-0.82}{0.82} \leq 2\hpr{X'}{0}{0.82},
\]
which liberally follows from Lemma~\ref{lem:seg-compare1} (and whose analog holds true in the entire range).


\subsection{Subcase $a_1 + a_2 + a_3 \geq 1$ and $a_1 \in (1/3, 0.387)$}

The proof in this case is a bit more complicated than in the other cases, and the demonstration we give does not capture the entire set of arguments we use. However it represents perhaps the most exotic argument, and features a semi-inductive argument along with a 5-elimination.

Assume
\[
a_1 = a_2 = a_3 = a_4 = a_5 = 0.34,
\]
so that 5-elimination (Lemma~\ref{lem:nm}) reduces us to proving the following inequality for all Rademacher sums $X'$ with $\var(X')=1$, whose largest weight is $\leq 0.34/(1-5\cdot 0.34^2)^{1/2} < 0.6$:
\begin{equation}\label{eq:demo3}
\begin{gathered}
	4\hpr{X'}{0}{1.01} + 5\hpr{X'}{0.04}{1.01} + \hpr{X'}{1.08}{2.06}
	\\ \geq \\
	\Pr[X' > 1.01] + 9\Pr[X' > 2.06] + 5\Pr[X' > 3.1] + \Pr[X' > 4.15].
\end{gathered}
\end{equation}
We prove~\eqref{eq:demo3} even with only the first term on the LHS. Using Chebyshev's inequality~\eqref{eq:cheby_our}:
\begin{equation}\label{eq:demo3-cheby}
	3\hpr{X'}{0}{1} \geq 9\Pr[X' > 2] + 15\Pr[X' > 3].
\end{equation}
In order to deduce~\eqref{eq:demo3} from~(\ref{eq:demo3-cheby}), we have to show
\begin{equation}\label{eq:demo3-final}
	\hpr{X'}{0}{1.01} \geq \Pr[X' > 1.01].
\end{equation}
This inequality is actually not easy to prove. However, it is implied by Tomaszewski's assertion~\eqref{eq:main} for the variable $X'$ which depends on $n-5$ weights (where $n$ is the number of weights in the original Rademacher sum $X$ we discuss)! We comment that in general we should use~\eqref{eq:dzin-intro1} instead of~\eqref{eq:main} to prove~\eqref{eq:demo3-final}, which is possible as~\eqref{eq:dzin-intro1} for $X'$ is implied from Tomaszewski's assertion~\eqref{eq:main} on $n-4$ weights.

\section{Open Problems}\label{sec:open}

As was mentioned in the introduction, we believe the methods developed in this paper can be applied to obtain further results on the distribution of Rademacher sums. We conclude the paper with several related open questions.

\paragraph{Tail bounds for Rademacher sums.} Consider the following general problem.
\newtheorem{problem}[theorem]{Problem}
\begin{problem}
Let $\mathcal{X}$ be the class of all Rademacher sums with variance $1$. Characterize the following function, defined for all $x \in \mathbb{R}$:
\[
	F(x) = \sup_{X \in \mathcal{X}} \Pr[X > x].
\]
\end{problem}
\noindent While different sub-cases of this problem were studied in many papers (see, e.g.,~\cite{Dzindzalieta14,Pinelis12} and the numerous references therein),
only a few exact results on it are known (e.g.,~\cite{BD15,Pinelis12}). Theorem~\ref{thm:main} continues the series of exact results, showing that $F(x) = 1/4$ for all $x \in [1, \sqrt{2})$.

A well-known conjecture, due to Hitczenko and Kwapie\'{n}~\cite{HK94}, concerns $F(x)$ for $x = -1$.
\begin{conjecture}[\cite{HK94}]\label{conj:olesz}
	Let $X = \sum a_i x_i$ be a Rademacher sum with $\var(X) = 1$. Then
	\[
		\Pr[X \geq 1] \geq \frac{7}{64}.
	\]
\end{conjecture}
Conjecture~\ref{conj:olesz} is an evident counterpart of Tomaszewski's conjecture -- while the latter states that $\Pr[X > 1]$ must be somewhat small, the former declares that $\Pr[X \geq 1]$ must be somewhat large.

The best currently known result toward Conjecture~\ref{conj:olesz} is $\Pr[X > 1] \geq 1/20$ (whenever $X \not \equiv x_1$), proved by Oleszkiewicz~\cite{Oles96} more than 20 years ago. Using our methods (specifically, Proposition~\ref{prop:Prawitz-Rademacher} and Lemma~\ref{lem:nm} with $m \leq 3$) and additional tools, Dvo{\v{r}}{\'{a}}k and the second author~\cite{DK21} proved the stronger bound $\Pr[X \geq 1] \geq 6/64$, along with the sharp bound $\Pr[X > 1] \geq \frac{1}{16}$.

\paragraph{Improved Berry-Esseen type bounds for Rademacher sums.}
Proposition~\ref{prop:ad-hoc2} shows that for a Rademacher sum $X=\sum a_i x_i$ with $\var(X) = 1$ and $0 \leq a_i\leq a_1=0.22$, and for any $x \geq 0$,
\[
\Pr[X \leq x] \geq \Pr[Z \leq x] - \Pr[Z \in \langle 0, a_1]],
\]
where $Z$ is a standard Gaussian. The following conjecture is a natural extension:
\begin{conjecture}
	Let $X = \sum a_i x_i$ be a Rademacher sum with $\var(X) = 1$ and $\forall i \colon 0 < a_i \leq a_1$. Let $Z \sim N(0, 1)$ be a standard Gaussian, and $x \in \mathbb{R}$. Then
	\begin{equation}\label{eq:be_conj}
		|\Pr[X \leq x] - \Pr[Z \leq x]| \leq \Pr[Z \in (0, a_1)] < \frac{1}{\sqrt{2\pi}} a_1.
	\end{equation}
\end{conjecture}
Note that first inequality in~\eqref{eq:be_conj} is tight, as is demonstrated by $X = \sum_{i=1}^{n} x_i / \sqrt{n}$ for $n$ odd, and $x=1/\sqrt{n}-\epsilon$
We note that it follows from~\cite[Theorem~1.3 and Remark~1.4(c)]{MS18} that for $X = \sum_{i=1}^{n} x_i / \sqrt{n}$, this inequality holds for any $n,x$.

It appears that our methods can be used to prove the conjecture in part of the range, namely,
$\Pr[Z \leq x] - \Pr[X \leq x] \leq \Pr[Z \in (0, a_1)]$ for all $x \geq 0$, in a way similar to the proof of Proposition~\ref{prop:ad-hoc2}.

\section*{Acknowledgements}

We thank Tom Kalvari, Jiange Li, Lunz Mattner, and Jeremy Schiff, and especially Ron Holzman, for inspiring discussions and useful suggestions.

