
\documentclass[12pt]{article}

\usepackage{e-jc}
\usepackage{amsthm,amsmath,amssymb}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
%\usepackage{hyperref}

\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}

\newtheorem*{main}{Main Theorem}

\newcommand{\abs}[1]{\left\lvert #1 \right\rvert}
\DeclareMathOperator*{\E}{\mathbb{E}}

\title{Tomaszewski's problem on\\randomly signed sums:\\breaking the 3/8 barrier}

\author{Ravi B. Boppana\\
\small Department of Mathematics\\[-0.8ex]
\small M. I. T.\\[-0.8ex]
\small Massachusetts, USA\\
\small\tt rboppana@mit.edu
\and
Ron Holzman\\
\small Department of Mathematics\\[-0.8ex]
\small Technion--Israel Institute of Technology\\[-0.8ex]
\small Israel\\
\small\tt holzman@tx.technion.ac.il
}

\date{\small Submitted: April 5, 2017\\
\small Mathematics Subject Classifications: 60C05, 05A20}

\begin{document}

\maketitle

\begin{abstract}
Let $v_1$, $v_2$, $\ldots\,$, $v_n$ be real numbers whose squares add up to~$1$.
Consider the $2^n$ signed sums of the form $S = \sum \pm v_i$.
Holzman and Kleitman (1992) proved that at least $\frac{3}{8}$ of these sums satisfy $\lvert S \rvert \le 1$.
This $\frac{3}{8}$ bound seems to be the best their method can achieve.
Using a different method, we improve the bound to $\frac{13}{32}$,
thus breaking the $\frac{3}{8}$ barrier.

\bigskip\noindent \textbf{Keywords:} combinatorial probability; probabilistic inequalities
\end{abstract}

\section{Introduction}

Let $v_1$, $v_2$, \dots, $v_n$ be real numbers such that the sum of their squares is at most~$1$.
Consider the $2^n$ signed sums of the form $S = \pm v_1 \pm v_2 \pm \dots \pm v_n$.
In 1986,
B.~Tomaszewski (see Guy~\cite{Guy}) asked the following question:
is it always true that at least $\frac{1}{2}$ of these sums
satisfy $\abs{S} \le 1$?
Most examples with $n = 2$ and $v_1^2 + v_2^2 = 1$ show that $\frac{1}{2}$ can't be replaced with a bigger number.

Holzman and Kleitman~\cite{HK} proved that at least $\frac{3}{8}$ of the sums satisfy $\abs{S} \le 1$.
This result was an immediate consequence of their main result:
at least $\frac{3}{8}$ of the sums satisfy the strict inequality $\abs{S} < 1$,
provided that each $\abs{v_i}$ is strictly less than~1.
This $\frac{3}{8}$ bound for $\abs{S} < 1$ is best possible:
consider the example with $n=4$ and $v_1 = v_2 = v_3 = v_4 = \frac{1}{2}$.
So $\frac{3}{8}$ seems to be a natural barrier to their method of proof.

Using a different method,
we prove that more than $\frac{13}{32}$ of the sums satisfy $\abs{S} \le 1$.
In other words, we break the $\frac{3}{8}$ barrier.
Our method, roughly speaking, goes like this.
We will let the first few $\pm$ signs be arbitrary.
But once the partial sum becomes near~1 in absolute value,
we will show that the final sum still has a decent chance of remaining at most~1 in absolute value.

We can actually improve the $\frac{13}{32}$ bound a tiny bit, to $\frac{13}{32} + 9 \times 10^{-6}$.  
Combining our method with other ideas, which could handle the tight cases for our analysis, may lead to further improvements of the bound. Still, the conjectured lower bound of $\frac{1}{2}$ currently appears to be out of reach.

Ten years after Holzman and Kleitman~\cite{HK} but independently,
Ben-Tal, Nemirovski, and Roos~\cite{BNR} proved that at least $\frac{1}{3}$ of the sums satisfy $\abs{S} \le 1$;
they say that the proof is mainly due to P.~van der Wal.
Shnurnikov~\cite{Shnurnikov} refined the argument of~\cite{BNR} to
prove a $36\%$ bound.
Even though these two bounds are weaker than that of Holzman and Kleitman,
the methods used to prove them are noteworthy.
In particular,
we will use the conditioning argument of~\cite{BNR}
and the fourth moment method of~\cite{Shnurnikov}.

Let Tomaszewski's constant be the largest constant~$c$ such that the fraction of sums that satisfy $\abs{S} \le 1$ is always at least~$c$.
We now know that Tomaszewski's constant is between $\frac{13}{32}$ and $\frac{1}{2}$.
Both \cite{HK} and \cite{BNR} conjecture that Tomaszewski's constant is $\frac{1}{2}$.
De, Diakonikolas, and Servedio~\cite{DDS} developed an algorithm to approximate Tomaszewski's constant.
Specifically, given an $\epsilon > 0$,
their algorithm will output a number that is within $\epsilon$ of Tomaszewski's constant.
The running time of their algorithm is exponential in $1/\epsilon^3$,
so it's not clear that we can run their algorithm in a reasonable amount of time to improve the known bounds
on Tomaszewski's constant.

The conjectured lower bound of $\frac{1}{2}$ has been confirmed in some special cases.
For example, von Heymann~\cite{Heymann} and Hendriks and van Zuijlen~\cite{HvZ} proved the conjecture when $n \le 9$.
Also, van Zuijlen~\cite{Zuijlen} and von Heymann~\cite{Heymann} proved the conjecture when all of the $\abs{v_i}$ are equal.  

We will use the language of probability.
Let $\Pr[A]$ be the probability of an event~$A$.
Let $\E(X)$ be the expected value of a random variable~$X$.
A \emph{random sign} is a random variable whose probability distribution is the uniform distribution on the set~$\{ -1, +1 \}$.
With this language, we can restate our main result.

\begin{main}
Let $v_1$, $v_2$, \dots, $v_n$ be real numbers such that $\sum_{i=1}^n v_i^2$ is at most~$1$.
Let $a_1$, $a_2$, \dots, $a_n$ be independent random signs.
Let $S$ be $\sum_{i = 1}^n a_i v_i$.
Then
$\Pr[ \abs{S} \le 1 ] > \frac{13}{32}.$
\end{main}

In Section~\ref{sec:initial_bound} of this paper,
we will provide a short proof of a bound better than~$\frac{3}{8}$.
In Section~\ref{sec:best_bound}, we will refine the analysis to improve the bound to~$\frac{13}{32}$ and slightly beyond.

\section{Beating the 3/8 bound}
\label{sec:initial_bound}

In this section,
we will give the simplest proof we can of a bound better than~$\frac{3}{8}$.
Namely, we will prove a bound of $\frac{37}{98}$,
which is a little more than $37.75\%$.
In Section~\ref{sec:best_bound},
we will improve the bound further.

We begin with a lemma.
Roughly speaking,
this lemma can be used to show that if a partial sum is a little less than~1,
then the final sum has a decent chance of remaining less than~1 in absolute value.

\begin{lemma} \label{lem:initial_bound}
Let $x$ be a real number such that $\abs{x} \le 1$.
Let $v_1$, $v_2$, \dots, $v_n$ be real numbers such that
\[
  \sum_{i = 1}^n v_i^2 \le \frac{2}{7} (1 + \abs{x})^2 .
\]
Let $a_1$, $a_2$, \dots, $a_n$ be independent random signs.
Let $Y$ be $\sum_{i=1}^n a_i v_i$.
Then
\[
  \Pr[ \abs{x + Y} \le 1 ] \ge \frac{37}{98} \, .
\]
\end{lemma}

\begin{proof}
By symmetry, we may assume that $x \ge 0$.
The fourth moment of~$Y$ is
\[
  \E(Y^4)
	  = 3 \Bigl( \sum_{i = 1}^n v_i^2 \Bigr)^2 - 2 \sum_{i = 1}^n v_i^4
	  \le 3 \Bigl( \sum_{i = 1}^n v_i^2 \Bigr)^2
		\le \frac{12}{49} (1 + x)^4 .
\]
So, by the fourth moment version of Chebyshev's inequality\footnote{Shnurnikov~\cite{Shnurnikov}
used the fourth moment in a similar situation.},
\[
  \Pr[\abs{Y} \ge 1 + x]
	  \le \frac{\E(Y^4)}{(1 + x)^4}
		\le \frac{12}{49} \, .
\]
Looking at the complement,
\[
  \Pr[\abs{Y} < 1 + x] \ge \frac{37}{49} \, .
\]
Because $Y$ has a symmetric distribution,
\[
  \Pr[-1 - x < Y \le 0]
	  \ge \frac{1}{2} \Pr[\abs{Y} < 1 + x]
		\ge \frac{37}{98} .
\]
Recall that $x \le 1$.
Hence if $-1 - x < Y \le 0$, then $\abs{x + Y} \le 1$.
Therefore
\[
  \Pr[ \abs{x + Y} \le 1 ]
		\ge \Pr[-1 - x < Y \le 0]
		\ge \frac{37}{98} \, .
\]
\end{proof}

Next we will use Lemma~\ref{lem:initial_bound} to go beyond the $\frac{3}{8}$ bound.

\begin{theorem} \label{thm:initial_bound}
Let $v_1$, $v_2$, \dots, $v_n$ be real numbers such that $\sum_{i=1}^n v_i^2$ is at most~$1$.
Let $a_1$, $a_2$, \dots, $a_n$ be independent random signs.
Let $S$ be $\sum_{i = 1}^n a_i v_i$.
Then
\[
  \Pr[ \abs{S} \le 1 ] \ge \frac{37}{98} \, .
\]
\end{theorem}

\begin{proof}
By inserting $0$'s,
we may assume that $n \ge 4$.
By permuting,
we may assume that the four largest $\abs{v_i}$ are
$\abs{v_n} \ge \abs{v_1} \ge \abs{v_{n-1}} \ge \abs{v_2}$.
By the quadratic mean inequality,
\[
  \frac{\abs{v_1} + \abs{v_2} + \abs{v_{n-1}} + \abs{v_n}}{4}
	  \le \sqrt{ \frac{v_1^2 + v_2^2 + v_{n-1}^2 + v_n^2}{4} }
		\le \sqrt{ \frac{1}{4} }
		= \frac{1}{2} \, .
\]
So $\abs{v_1} + \abs{v_2} + \abs{v_{n-1}} + \abs{v_n} \le 2$.
Because of our ordering,
\[
  \abs{v_1} + \abs{v_2}
	  \le \frac{\abs{v_1} + \abs{v_n}}{2} + \frac{\abs{v_2} + \abs{v_{n-1}}}{2}
		\le 1.
\]

Given an integer~$t$ from $0$ to $n$,
let $X_t$ be the partial sum~$\sum_{i=1}^t a_i v_i$
and let $Y_t$ be the remaining sum~$\sum_{i = t + 1}^n a_i v_i$.
Let $T$ be the smallest nonnegative integer~$t$ such that
$t = n - 1$ or $\abs{X_t} > 1 - \abs{v_{t + 1}}$.
In a stochastic process such as ours,
$T$ is called a stopping time, defined by the stopping rule in the previous sentence\footnote{A similar stopping rule
was implicitly used by Ben-Tal \emph{et al.}~\cite{BNR} and refined by Shnurnikov~\cite{Shnurnikov}.
In addition, \cite{Shnurnikov} pointed out the value of having $\abs{v_1} + \abs{v_2} \le 1$.}.
Note that $T \ge 2$, since $\abs{v_1} + \abs{v_2} \le 1$.
By the stopping rule, $\abs{X_{T - 1}} \le 1 - \abs{v_T}$.
Hence by the triangle inequality,
\[
  \abs{X_T}
		\le \abs{X_{T-1}} + \abs{v_T}
		\le 1 - \abs{v_T} + \abs{v_T}
		= 1.
\]
Also by the stopping rule, if $T < n - 1$, then $\abs{X_T} > 1 - \abs{v_{T + 1}}$.

We will condition on $T$ and $X_T$.
We claim that
\[
  \Pr[\abs{S} \le 1 \mid T, X_T ] \ge \frac{37}{98} \, .
\]
By averaging over $T$ and $X_T$,
this claim implies the theorem.
To prove the claim, we may assume by symmetry that $X_T \ge 0$.
We will divide the proof of the claim into three cases, depending on~$T$.

\medskip

\textbf{Case 1:}
$T = n - 1$.
In this case, $\abs{Y_T} = \abs{v_n} \le 1$.
Recall that $0 \le X_T \le 1$.
Hence if $Y_T \le 0$, then $\abs{S} = \abs{X_T + Y_T} \le 1$.
Therefore by symmetry,
\[
  \Pr[\abs{S} \le 1 \mid T, X_T ]
		\ge \Pr[ Y_T \le 0 \mid T, X_T ]
		\ge \frac{1}{2} \, .
\]

\medskip

\textbf{Case 2:}
$T = n - 2$.
In this case,
\[
  \abs{Y_T}
	  \le \abs{v_{n-1}} + \abs{v_n}
		\le 2 - \abs{v_1}
		\le 2 - \abs{v_{n - 1}}.
\]
Recall that $1 - \abs{v_{n-1}} < X_T \le 1$.
Hence if $Y_T \le 0$,
then $\abs{S} = \abs{X_T + Y_T} \le 1$.
Therefore by symmetry,
\[
  \Pr[\abs{S} \le 1 \mid T, X_T ]
		\ge \Pr[ Y_T \le 0 \mid T, X_T ]
		\ge \frac{1}{2} \, .
\]

\medskip

\textbf{Case 3:}
$T \le n - 3$.
In this case, by the stopping rule,
\[
  \sum_{i = T + 1}^n v_i^2
	  \le 1 - \sum_{i = 1}^T v_i^2
		\le 1 - v_1^2 - v_2^2
		\le 1 - 2 v_{T + 1}^2
		< 1 - 2(1 - X_T)^2 .
\]
We can bound the final expression as follows:
\[
  1 - 2(1 - X_T)^2
	  = \frac{2}{7} (1 + X_T)^2 - \frac{1}{7} (4 X_T - 3)^2
		\le \frac{2}{7} (1 + X_T)^2 .
\]
Hence the hypotheses of Lemma~\ref{lem:initial_bound} are satisfied with $x = X_T$ and $Y = Y_T$.
By Lemma~\ref{lem:initial_bound}, we conclude that
\[
  \Pr[\abs{S} \le 1 \mid T, X_T ]
	  = \Pr[ \abs{X_T + Y_T} \le 1 \mid T, X_T ]
		\ge \frac{37}{98} \, .
\]
\end{proof}

\section{Further improvement}
\label{sec:best_bound}

In this section, we will improve the lower bound to~$\frac{13}{32}$, which is $40.625\%$.
At the end, we will sketch how to improve the bound further, to $\frac{13}{32} + 9 \times 10^{-6}$.

Let us examine where the proof of Theorem~\ref{thm:initial_bound} is potentially tight.
Looking at its Case~3, we see that the proof is potentially tight when $T = 2$
and $\abs{v_1} = \abs{v_2} = \abs{v_3} = \frac{1}{4}$.
But that scenario is impossible: if $T = 2$, then by the stopping rule, $\abs{v_1} + \abs{v_2} > 1 - \abs{v_3}$.
This suggests that we can sharpen the bound on $\sum_{i=T+1}^n v_i^2$ in terms of $T$ and $X_T$.

Another idea is that our final bound on $\Pr[\abs{S} \le 1]$, instead of being the worst-case conditional bound, may be taken to be a weighted average of the conditional bounds, with weights corresponding to the distribution of $T$.

First, we state the following generalization of Lemma~\ref{lem:initial_bound}.
Given a number~$c$, define $F(c)$ by
\[
  F(c) = \frac{1}{2} ( 1 - 3 c^2 ) .
\]

\begin{lemma} \label{lem:best_bound}
Let $c$ be a nonnegative number.
Let $x$ be a real number such that $\abs{x} \le 1$.
Let $v_1$, $v_2$, \dots, $v_n$ be real numbers such that
\[
  \sum_{i = 1}^n v_i^2 \le c (1 + \abs{x})^2 .
\]
Let $a_1$, $a_2$, \dots, $a_n$ be independent random signs.
Let $Y$ be $\sum_{i=1}^n a_i v_i$.
Then
\[
  \Pr[ \abs{x + Y} \le 1 ] \ge F(c) .
\]
\end{lemma}

\begin{proof}
By symmetry, we may assume that $x \ge 0$.
As in the proof of Lemma~\ref{lem:initial_bound}, the fourth moment of~$Y$ satisfies
\[
  \E(Y^4)
	  \le 3 \Bigl( \sum_{i=1}^n v_i^2 \Bigr)^{2}
		\le 3 c^{2} (1 + x)^4 .
\]
So, by the fourth moment version of Chebyshev's inequality,
\[
  \Pr[\abs{Y} \ge 1 + x]
	  \le \frac{\E(Y^4)}{(1 + x)^4}
		\le  3 c^{2} .
\]
Following the proof of Lemma~\ref{lem:initial_bound}, by taking the complement and then using the symmetry of~$Y$,
we have
\[
  \Pr[ \abs{x + Y} \le 1 ] \ge \frac{1}{2} ( 1 - 3 c^{2} ) = F(c) .
\]
\end{proof}

Now we will use Lemma~\ref{lem:best_bound} to prove our $\frac{13}{32}$ lower bound.  

\begin{theorem}  \label{thm:best_bound}
Let $v_1$, $v_2$, \dots, $v_n$ be real numbers such that $\sum_{i=1}^n v_i^2$ is at most~$1$.
Let $a_1$, $a_2$, \dots, $a_n$ be independent random signs.
Let $S$ be $\sum_{i = 1}^n a_i v_i$.
Then
\[
  \Pr[ \abs{S} \le 1 ] > \frac{13}{32}.
\]
\end{theorem}

\begin{proof}
By inserting $0$'s,
we may assume that $n \ge 4$.
By symmetry, we may assume that each $v_i$ is nonnegative.
By permuting,
we may assume that the $v_i$ are ordered as follows:
\[
  v_n \ge v_1 \ge v_{n-1} \ge v_2 \ge v_3 \ge \dots \ge v_{n-2} .
\]
Except for the oddballs $v_n$ and $v_{n-1}$, the order is decreasing.
As in Theorem~\ref{thm:initial_bound},
we have $v_1 + v_2 + v_{n-1} + v_n \le 2$
and $v_1 + v_2 \le 1$.

Given an integer~$t$ from $0$ to $n$,
let $M_t$ be the sum~$\sum_{i=1}^t v_i$.
Let $K$ be the smallest nonnegative integer~$t$ such that
$t = n - 1$ or $M_t > 1 - v_{t + 1}$.
The parameter~$K$ measures how spread out the $v_i$ are.
Note that $K \ge 2$, since $v_1 + v_2 \le 1$.
By the definition of~$K$, observe that $M_{K - 1} \le 1 - v_K$ and hence $M_K \le 1$.
Also, if $K < n - 1$, then $M_K > 1 - v_{K + 1}$ and hence $M_{K + 1} > 1$.

Given an integer~$t$ from $0$ to $n$,
define the sums $X_t$ and $Y_t$ as in Theorem~\ref{thm:initial_bound}.
Note that $\abs{X_t} \le M_t$.
Following Theorem~\ref{thm:initial_bound}, let $T$ be the smallest nonnegative integer~$t$ such that
$t = n - 1$ or $\abs{X_t} > 1 - v_{t + 1}$.
Note that $T \ge K$.
As before, we have $\abs{X_{T - 1}} \le 1 - v_T$ and $\abs{X_T} \le 1$.
Also, if $T < n - 1$, then $\abs{X_T} > 1 - v_{T + 1}$.

We will bound from below the conditional probability $\Pr[\abs{S} \le 1 \mid T ]$.
Namely, we will prove the two-piece lower bound
\[
  \Pr[\abs{S} \le 1 \mid T ] \ge
		\begin{cases}
		  F\left( \frac{(K + 1)^2 - T}{(2K + 1)^2} \right)  &  \textrm{if } T \le \frac{3K+2}{2} \, ; \\
			F\left( \frac{K}{4K + 2} \right)                  &  \textrm{if } T \ge \frac{3K+2}{2} \, .
		\end{cases}
\]
We will actually prove the same lower bound on the refined conditional probability $\Pr[\abs{S} \le 1 \mid T, X_T ]$.
To prove this claim,
we may assume by symmetry that $X_T \ge 0$.
We will divide the proof of the claim into five cases, depending on~$T$.

\medskip

\textbf{Case 1:} $T = n - 1$.
The proof of this case is the same as Case~1 of Theorem~\ref{thm:initial_bound},
which yields the stronger bound $\Pr[\abs{S} \le 1 \mid T, X_T ] \ge \frac{1}{2}$.

\medskip

\textbf{Case 2:} $T = n - 2$.
The proof of this case is the same as Case~2 of Theorem~\ref{thm:initial_bound},
which yields the stronger bound $\Pr[\abs{S} \le 1 \mid T, X_T ] \ge \frac{1}{2}$.

\medskip

\textbf{Case 3:} $K + 1 \le T \le \frac{3K + 2}{2}$ and $T \le n - 3$.
By the quadratic mean inequality,
\[
  \sum_{i = 1}^{K + 1} v_i^2
	  \ge \frac{1}{K + 1} \Bigl( \sum_{i = 1}^{K + 1} v_i \Bigr )^2
		= \frac{1}{K + 1} M_{K + 1}^2
		> \frac{1}{K + 1} \, .
\]
Hence, by splitting our sum into two parts, we get
\[
  \sum_{i = 1}^T v_i^2
		> \frac{1}{K + 1} + (T - K - 1) v_{T + 1}^2
		\ge \frac{1}{K + 1} + (T - K - 1) (1 - X_T)^2 .
\]
As a simpler bound,
\[
  \sum_{i = 1}^T v_i^2
	  \ge T v_{T + 1}^2
		> T (1 - X_T)^2 .
\]
Multiplying the second-to-last inequality by $\frac{2T - K - 1}{2K + 1}$ and the last inequality by $\frac{3K + 2 - 2T}{2K + 1}$,
both multipliers being nonnegative by the case assumption, we get
\[
  \sum_{i = 1}^T v_i^2
	  \ge \frac{2T - K - 1}{(K + 1)(2K + 1)} + \frac{(K + 1)^2 - T}{2K + 1} (1 - X_T)^2 .
\]
Therefore, looking at the complementary sum, we get
\[
  \sum_{i = T+1}^n v_i^2
	  \le \frac{(K + 1)^2 - T}{(K + 1)(2K + 1)} \left[ 2 - (K + 1)(1 - X_T)^2 \right] .
\]
We can bound the bracketed expression as follows:
\begin{align*}
  2 - (K + 1)(1 - X_T)^2
	  &= \frac{K+ 1}{2K + 1} (1 + X_T)^2 - \frac{2}{2K+ 1} \left[ (K + 1) X_T - K \right]^2 \\
		&\le \frac{K + 1}{2K + 1} (1 + X_T)^2 .
\end{align*}
Plugging this inequality back into the previous one, we get
\[
  \sum_{i = T+1}^n v_i^2
	  \le \frac{(K + 1)^2 - T}{(2K + 1)^2} (1 + X_T)^2 .
\]
Hence the hypotheses of Lemma~\ref{lem:best_bound} are satisfied with $c = \frac{(K + 1)^2 - T}{(2K + 1)^2}$,
$x = X_T$, and $Y = Y_T$.
By Lemma~\ref{lem:best_bound}, we conclude that
\[
  \Pr[\abs{S} \le 1 \mid T, X_T ]
		= \Pr[ \abs{X_T + Y_T} \le 1 \mid T, X_T ]
		\ge F\Bigl( \frac{(K + 1)^2 - T}{(2K + 1)^2} \Bigr) .
\]

\medskip

\textbf{Case 4:} $\frac{3K + 2}{2} \le T \le n - 3$.
As in Case~3,
we can bound $\sum_{i = 1}^T v_i^2$ as follows:
\[
  \sum_{i = 1}^T v_i^2
		> \frac{1}{K + 1} + (T - K - 1) (1 - X_T)^2 .
\]
Because $T \ge \frac{3K + 2}{2}$, this inequality implies
\[
  \sum_{i = 1}^T v_i^2
		\ge \frac{1}{K + 1} + \frac{K}{2} (1 - X_T)^2 .
\]
Compare this bound with the combined bound from Case~3:
\[
  \sum_{i = 1}^T v_i^2
	  \ge \frac{2T - K - 1}{(K + 1)(2K + 1)} + \frac{(K + 1)^2 - T}{2K + 1} (1 - X_T)^2 .
\]
Note that our bound on $\sum_{i=1}^T v_i^2$ is the same as this bound from Case~3 when $T = \frac{3K + 2}{2}$.
So we can repeat the remainder of Case~3 to get the same lower bound on $\Pr[\abs{S} \le 1 \mid T, X_T ]$ when $T = \frac{3K + 2}{2}$.
The bound on $\Pr[\abs{S} \le 1 \mid T, X_T ]$ in Case~3 was
\[
  \Pr[\abs{S} \le 1 \mid T, X_T ]
		\ge F\Bigl( \frac{(K + 1)^2 - T}{(2K + 1)^2} \Bigr).
\]
When $T = \frac{3K + 2}{2}$, this bound becomes
\[
  \Pr[\abs{S} \le 1 \mid T, X_T ]
		\ge F \Bigl( \frac{K}{4K + 2} \Bigr) .
\]		
So we get the same bound in our current case.

\medskip

\textbf{Case 5:} $T = K \le n - 3$.
By the quadratic mean inequality,
\[
  \sum_{i = 1}^{T} v_i^2
	  \ge \frac{1}{T} \Bigl( \sum_{i = 1}^{T} v_i \Bigr )^2
		= \frac{1}{T} M_{T}^2
		\ge \frac{1}{T} X_{T}^2
		= \frac{1}{K} X_T^2 .
\]
We can bound the final expression as follows:
\begin{align*}
  \frac{1}{K} X_T^2
	  &= \frac{1}{K + 1} - (1 - X_T)^2 + \frac{1}{K(K + 1)} \left[ (K + 1) X_T - K \right]^2 \\
		&\ge \frac{1}{K + 1} - (1 - X_T)^2 .
\end{align*}
Plugging this inequality back into the previous one, we get
\[
  \sum_{i = 1}^{T} v_i^2
	  \ge \frac{1}{K + 1} - (1 - X_T)^2
		= \frac{1}{K + 1} + (T - K - 1) (1 - X_T)^2 .
\]
This is the same inequality we derived at the beginning of Case~3.
So we can repeat the remainder of Case~3 to get the same lower bound:
\[
  \Pr[\abs{S} \le 1 \mid T, X_T ]
    \ge  F\Bigl( \frac{(K + 1)^2 - T}{(2K + 1)^2} \Bigr) .
\]

\medskip

In summary, we have proved our claim on conditional probability:
\[
  \Pr[\abs{S} \le 1 \mid T ] \ge
		\begin{cases}
		  F\left( \frac{(K + 1)^2 - T}{(2K + 1)^2} \right)  &  \textrm{if } T \le \frac{3K+2}{2} \, ; \\
			F\left( \frac{K}{4K + 2} \right)                  &  \textrm{if } T \ge \frac{3K+2}{2} \, .
		\end{cases}
\]
Next, we will use this conditional bound to derive a lower bound on the unconditional probability $\Pr[\abs{S} \le 1]$.

As mentioned above, we always have $T \ge K$.
In fact, assuming that $K \le n-4$, we have $T=K$ if the signs $a_1$, \dots, $a_K$ are all equal, and otherwise $T \ge K+2$.
This follows from observing that if $a_1$, \dots, $a_K$ are not all equal,
then $\abs{X_K} \le \sum_{i=1}^{K-1} v_i - v_K \le 1 - v_{K+1}$ and $\abs{X_{K+1}} \le \sum_{i=1}^{K-1} v_i - v_K + v_{K+1} \le 1 - v_{K+2}$, by the definition of $K$ and the ordering of the $v_i$.

This shows that for $K \le n-4$ we have $\Pr[T=K]=\frac{1}{2^{K-1}}$ and $\Pr[T \ge K+2]=1-\frac{1}{2^{K-1}}$. Therefore
\begin{align*}
\Pr[&\abs{S} \le 1] \\
  &= \frac{1}{2^{K-1}} \Pr[\abs{S} \le 1 \mid T=K] + \Bigl( 1 - \frac{1}{2^{K-1}} \Bigr) \Pr[\abs{S} \le 1 \mid T \ge K+2] \\
  &\ge \frac{1}{2^{K-1}} F\left( \frac{(K + 1)^2 - K}{(2K + 1)^2} \right)
	   + \Bigl(1 - \frac{1}{2^{K-1}} \Bigr) F\left( \frac{(K + 1)^2 - (K+2)}{(2K + 1)^2} \right).
\end{align*}
Here we have used our conditional bounds, the fact that they are nondecreasing in $T$, and the inequality $K+2 \le \frac{3K+2}{2}$. Note that this lower bound on $\Pr[\abs{S} \le 1]$ remains valid without assuming that $K \le n-4$. Indeed, if $K=n-3$ it is still true that $\Pr[T=K] = \frac{1}{2^{K-1}}$, and while $T=K+1=n-2$ may occur in this case, it yields a conditional bound of $\frac{1}{2}$ as shown in Case~2 above, which is even better than our stated lower bound. The values $n-2$ and $n-1$ for $K$ are of course covered by the conditional bound of $\frac{1}{2}$ in Cases 1 and 2 above.

Thus, to conclude our proof it suffices to show that
\[
  \frac{1}{2^{K-1}} F\left( \frac{(K + 1)^2 - K}{(2K + 1)^2} \right)
	  + \Bigl(1 - \frac{1}{2^{K-1}} \Bigr) F\left( \frac{(K + 1)^2 - (K+2)}{(2K + 1)^2} \right)
		  > \frac{13}{32}
\]
holds for all $K \ge 2$. Substituting the relevant expressions into the formula for $F$ and performing routine manipulations, the latter is shown to be equivalent to
\[ 64(K^2 + K) < 2^{K-1} (40K^2 + 40K - 15), \]
which indeed holds for $K \ge 2$.
\end{proof}

Can we improve this $\frac{13}{32}$ lower bound?
Yes, a little.  
The idea is to replace the fourth moment with the more flexible $p$th moment,
where $p$ is a parameter to be optimized.
To do so, we will need Khintchine's inequality.
This inequality was first proved by Khintchine~\cite{Khintchine} in a weaker form
and later proved by Haagerup~\cite{Haagerup} with the optimal constants.
Namely, given $p \ge 2$,
let $B_p$ be the constant
\[
  B_p = \frac{2^{p/2} \Gamma(\frac{p + 1}{2})}{\sqrt{\pi}} \, ,
\]
where $\Gamma$ is the gamma function.
For example, $B_2 = 1$, $B_3 = 2 \sqrt{2/\pi}$, and $B_4 = 3$.

\begin{theorem}[Khintchine's inequality] \label{thm:khintchine}
Let $p$ be a real number such that $p \ge 2$.
Let $v_1$, $v_2$, \dots, $v_n$ be real numbers.
Let $a_1$, $a_2$, \dots, $a_n$ be independent random signs.
Let $S$ be $\sum_{i = 1}^n a_i v_i$.
Then
\[
  \E(\abs{S}^p) \le B_p \Bigl( \sum_{i=1}^n v_i^2 \Bigr)^{p/2} .
\]
\end{theorem}

For the improved lower bound, choose with foresight $p = 3.95937$.
In Lemma~\ref{lem:best_bound}, replace the fourth moment with the $p$th moment 
and apply Khintchine's inequality (with $S = Y$),
which allows us to replace the function~$F$ with the function~$G$ defined by 
$G(c) = \frac{1}{2} ( 1 - B_p c^{p/2} )$.
Use this revised lemma in Theorem~\ref{thm:best_bound}.     
The resulting lower bound is~$G(\frac{1}{4})$, which is bigger than $\frac{13}{32} + 9 \times 10^{-6}$.  
We omit the details.  

\begin{thebibliography}{99}

\bibitem{BNR}
A. Ben-Tal, A. Nemirovski, and C. Roos.
\newblock Robust solutions of uncertain quadratic and conic-quadratic problems.
\newblock \emph{{SIAM} Journal on Optimization}, 13(2):535--560, 2002.

\bibitem{DDS}
A. De, I. Diakonikolas, and R. A. Servedio.
\newblock A robust {K}hintchine inequality,
and algorithms for computing optimal constants in {F}ourier analysis and high-dimensional geometry.
\newblock \emph{{SIAM} Journal on Discrete Mathematics}, 30(2):1058--1094, 2016.

\bibitem{Guy}
R. K. Guy.
\newblock Any answers anent these analytical enigmas?.
\newblock \emph{American Mathematical Monthly}, 93(4):279--281, 1986.

\bibitem{Haagerup}
U. Haagerup.
\newblock The best constants in the {K}hintchine inequality.
\newblock \emph{Studia Mathematica}, 70(3):231--283, 1981.

\bibitem{HvZ}
H. Hendriks and M. C. A. van Zuijlen.
\newblock Linear combinations of {R}ademacher random variables.
\newblock \arxiv{1703.07251v1}, 2017.

\bibitem{Heymann}
F. von Heymann.
\newblock Ideas for an old analytic enigma about the sphere that fail in intriguing ways.
\newblock \url{http://www.mi.uni-koeln.de/opt/wp-content/uploads/2017/02/Cube_sphere.pdf}, 2012.  

\bibitem{HK}
R. Holzman and D. J. Kleitman.
\newblock On the product of sign vectors and unit vectors.
\newblock \emph{Combinatorica}, 12(3):303--316, 1992.

\bibitem{Khintchine}
A. Khintchine.
\newblock {\"U}ber dyadische {B}r{\"u}che.
\newblock \emph{Math.\ Zeitschrift}, 18:109--116, 1923.

\bibitem{Shnurnikov}
I. Shnurnikov.
\newblock On a sum of centered random variables with nonreducing variances.
\newblock \arxiv{1202.2990v2}, 2012.

\bibitem{Zuijlen}
M. C. A. van Zuijlen.
\newblock On a conjecture concerning the sum of independent {R}ademacher random variables.
\newblock \arxiv{1112.4988v1}, 2011.

\end{thebibliography}
\end{document} 