\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P40}{19(4)}{2012}
\usepackage{algcompatible}
\usepackage{amsmath,amsthm,amssymb,amsfonts,algorithm}
\usepackage{xspace,graphicx}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

\def\mathbi#1{\textbf{\em #1}}
\newcommand{\vn}{\vec{\mathbi{n}}}
\newcommand{\vu}{\vec{\mathbf{1}}}
\newcommand{\vz}{\vec{\mathbf{0}}}
\newcommand{\mz}{\mathbf{0}}
\newcommand{\M}{M\"{u}nchhausen\xspace}
\renewcommand{\O}{\mathop{\mathrm{O}}}
\newcommand{\Om}{\mathop{\mathrm{\Omega}}}
\newcommand{\Th}{\mathop{\mathrm{\Theta}}}
\renewcommand{\o}{\mathop{\mathrm{o}}}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\abs}[1]{\left| #1 \right|}
\newcommand{\argmax}{\operatornamewithlimits{argmax}}
\newcommand{\defeq}{\stackrel{\text{def}}{=}}
\newcommand{\setN}{\mathbb{N}}
\newcommand{\setB}{\mathbb{B}}
\newcommand{\setP}{\mathbb{P}}
\newcommand{\setS}{\mathbb{S}}
\newcommand{\weigheq}{\stackrel{?}{=}}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}
\newtheorem{claim}{Claim}
\newtheorem{construct}{Hypothetical Construct}
\newtheorem{lem}{Lemma}[section]
\newtheorem{cor}{Corollary}[section]

\renewcommand{\P}{\mathbb{P}}
\newcommand{\E}{\mathbb{E}}

\renewcommand{\algorithmicensure}{\textbf{return}}

\title{\bf M\"{u}nchhausen Matrices}
\author{Michael Brand\\
\small Faculty of Information Technology\\[-0.8ex]
\small Monash University\\[-0.8ex]
\small Clayton, VIC, Australia\\
\small\tt michael.brand@alumni.weizmann.ac.il
}

\date{\dateline{May 10, 2012}{Nov 27, 2012}{Dec 13, 2012}\\
\small Mathematics Subject Classifications: 11B83, 05B20, 05B30, 05-04}

\begin{document}

\maketitle

\begin{abstract}
``The Baron's omni-sequence'', $B(n)$, first defined by Khovanova and Lewis
(2011), is a sequence that gives for each $n$
the minimum number of weighings on balance
scales that can verify the correct labeling of $n$ identically-looking
coins with distinct integer weights between $1$ gram and $n$ grams.

A trivial lower bound on $B(n)$ is $\log_3 n$, and it has been shown that
$B(n)$ is $\O(\log n)$.

We introduce new theoretical tools for the study of this problem, 
and show that $B(n)$ is $\log_3 n + \O(\log \log n)$, thus
settling in the affirmative a conjecture by Khovanova and Lewis that the true
growth rate of the sequence is very close to the natural lower bound.

\bigskip\noindent \textbf{Keywords:} Baron's Omni-sequence; Munchausen;
coin weighing; verification
\end{abstract}

\section{Introduction and definitions}
Coin-weighing puzzles have been abundantly discussed in the mathematical
literature over the past 60 years
(see, e.g.\ \cite{Steinhaus:snapshots,Halbeisen:general_counterfeit,
Smith:counterfeit,Dyson:Pennies}). In coin-weighing problems one must typically
identify a counterfeit coin from a set of identically-looking coins by use of
balance scales, utilizing the knowledge that the counterfeit coin has
distinctive weight. This can be generalized to the problem of identifying a
coin, or a subset of the coins, based on distinctive weight characteristics,
or, alternatively, to the problem of establishing the weight of a
given coin.

This paper relates to a different kind of coin-weighing puzzle, which we call
the \M coin-weighing problem.
Consider the following question: given $n$ coins with distinct
integer weights between $1$ gram and $n$ grams, each labeled by a distinct
integer label between $1$ and $n$, what is the minimum number of weighings
of these $n$ coins on balance scales that can prove unequivocally that all
coins are labeled by their correct weight?

This question differs from classic coin-weighing problems in that we do not
need to \emph{discover} the weights, but only to determine whether or not
a given labeling of weights is the correct one. To establish the weights one
would require $\Om(n \log{n})$ weighings (as can be proved by reasoning similar
to that which establishes lower bounds for comparative sorting
\cite{Knuth:programming,Cormen:algorithms}), whereas merely
verifying an existing labeling can be performed trivially in $\O(n)$
weighings.

This question, which was inspired by a riddle that appeared in the
Moscow Mathematical
Olympiad \cite{Tokarev:Olympiad}, gives rise to an integer sequence, $B(n)$,
that was studied in \cite{Khovanova:Baron} and was dubbed there ``The Baron's
omni-sequence''. It appears as sequence A186313 in the On-line Encyclopedia of
Integer Sequences \cite{A186313:Omnisequence}.

The present paper takes the view that, in studying this and related topics,
\cite{Khovanova:Baron} and \cite{Khovanova:Sequence} uncovered the tip of an
iceberg, under which lies a wealth of hitherto unexplored mathematical questions
that belong to a new class of problems. Namely, these are
``verification problems''.

In the remaining parts of this section, we define some terminology regarding
weighings. The definitions present the subject of verification as resembling
a design problem, and demonstrate how verification can be considered as a
matrix property. The section will conclude with a re-definition of $B(n)$ as a
special case and a formulation of the problem statement.

In Section \ref{S:special} we develop new analytical tools which we believe to
be of importance in a range of verification problems. We begin by presenting
a simplified version of the tools. These allow the construction of matrices
with the desired properties, but only for matrices whose dimensions
satisfy certain conditions. For $n$ values that satisfy these special
conditions, the constructions prove an upper bound on
$B(n)$ that is tighter than the best previously-known bound.

In Section \ref{S:general}, the tools developed previously are embellished.
Further complications allow their use for matrices with general widths.
We note that in both Section \ref{S:special} and Section \ref{S:general}
the techniques used, even with the extra features, are fairly generic in
what they accomplish and are straightforward to apply to other problems.
Unfortunately, proving that the algorithms terminate successfully for any
specific case, such as the \M coin-weighing problem, and, furthermore, proving
bounds on their outputs for specific cases, does necessitate a certain
level of technical detail, which forms large parts of the sections.

Lastly, in Section \ref{S:bound}, we put the new tools to full use,
designing with them an efficient strategy for solving the \M coin-weighing
problem for any $n$. Our main theorems are proved by
calculating the bound on $B(n)$ that this strategy implies.

\subsection{Weigh-sets}
First, we introduce the following notations. Let $\vn$ be the vector
$(1,\ldots,n)^T$, $\vu_n$ be the $n\times 1$ all-ones vector and
$\vz_n$ be the $n\times 1$ all-zeros vector,
where the subscript $n$ may be omitted from the latter two notations
when it is clear from the context.
The name of a vector will also be used for its elements. For example, if
$\vec{v}$ is a vector of length $s$, its elements will be denoted as
$(v_1,\ldots,v_s)$. For a matrix, $M$, $M_{ij}$ is its element in the $i$'th
row and $j$'th column, where index counting begins with $1$.
$M_{i*}$ and $M_{*j}$ signify
the $i$'th row and the $j$'th column of $M$, respectively.

For a set of coins $X$, a \emph{weighing} can be described by an unordered pair
of disjoint subsets of $X$, $\{L,R\}$. Set $L$ is
conceptually the subset placed on one pan of the balance scales and set $R$ is
placed on the other pan. Similarly, a \emph{weigh-set} can be described as a
set of weighings. Thus, the definition of a weigh-set of $X$ as a set of
unordered pairs of disjoint subsets of $X$ is possibly reminiscent of the
definition of a design (most generally describable as a set of disjoint subsets
of some base set $X$). Like in the case of designs, it is often convenient to
discuss weighings and weigh-sets in matrix notation. Consider the following.

If the elements of the set $X$ are indexed $1,\ldots,n$, a vector $\vec{v}$ of
length $n$ with entries in $\{-1,0,1\}$ represents a weighing by placing in $L$
all elements of $X$ whose indices have a $-1$ entry in $\vec{v}$, and placing
in $R$ all those whose indices have a $1$ entry. Similarly, an $m \times n$
matrix, $M$, with entries in $\{-1,0,+1\}$ represents a weigh-set composed
of $m$ weighings: each row represents a weighing.
(Note: this weigh-set in matrix
notation should not be confused with a ``weighing matrix'', defined in
\cite{Mood:Hotelling}, which relates to a different type of weighing problem.)

Clearly, the matrix notation has redundant information. The order of the rows
can be permuted arbitrarily and each row can be inverted. A weigh-set matrix
should therefore be taken as a representative of an entire set of possible
representations of the same weigh-set.
In this paper, we use set and matrix notation interchangeably when discussing
weigh-sets. For example, though the variable $M$ is always a matrix, the
terminology ``weigh-set $M$'' should be taken as short-hand for
``a weigh-set represented by matrix $M$''.

Suppose that $X$ is a set of $n$ coins, in which the $i$'th coin weighs $x_i$.
In the weigh-set $M$, the vector that is the result of the product
$M\vec{x}$ describes the $m$ imbalances in the $m$ weighings described by $M$.
On balance scales, we typically get the information of the sign of each entry
in $M\vec{x}$. However, in other scenarios we may consider having more
information (such as full information on the imbalance) or less (just the binary
information of whether or not the two pans balance, omitting the sign
information of any imbalance).

A weigh-set $M$ is a \emph{verification} for the set $X$ with
elements whose weights are described by the vector $\vec{x}$
if the vector of signs of the elements of
$M\vec{x}$ is unique among all $M\vec{y}$ where $\vec{y}$ is a
permutation of $\vec{x}$.
A matrix (weigh-set) that is a verification of the
coins weighing $1,\ldots,n$ grams is a \emph{\M weigh-set} or \emph{\M matrix}.

In addition, one can also consider ``partial verifications''.
We say that a weigh-set, $M$, \emph{establishes} a partition of
$X$ if the vector of signs of the elements of $M\vec{x}$ is different to that
of any $M\vec{y}$
where $\vec{y}=\sigma(\vec{x})$ and $\sigma$ is a permutation that
does not respect the partition.

By contrast, we say that the weigh-set verifies $X$ \emph{subject to} the
partition if the vector of signs of the elements of $M\vec{x}$ is unique among
all $M\vec{y}$ where $\vec{y}=\sigma(\vec{x})$ and $\sigma$ is a permutation
that \emph{does} respect the partition.

If $A$ is a weigh-set that establishes some partition, $P$, of $X$, and $B$ is a
weigh-set that verifies $X$ subject to it, $A \cup B$ is a verification of $X$.

\subsection{The Baron's omni-sequence}
\emph{The Baron's omni-sequence} is the sequence whose $n$'th term, $B(n)$,
is the minimum number for which there exists a $B(n)\times n$
\M matrix.

A trivial lower bound for $B(n)$ is $\log_3 n$. This bound is attained from the
observation that there are at most $3^m$ distinct columns in an $m \times n$
$\{-1,0,1\}$-matrix, and a \M matrix cannot have duplicate columns,
because if any two columns, $i$ and $j$, were identical, permuting the coins
by replacing the $i$'th and $j$'th coin would not have affected the weighing
results.

In \cite{Khovanova:Baron}, Khovanova and Lewis construct $m \times n$
\M matrices with $m\le\alpha \log_3 n + C$ for some constant $C$ and an
$\alpha$ value of approximately $2.96$. This has since been improved to
$\alpha=2$ in \cite{Brand:Tightening}, reducing the gap between the theoretical
lower bound and the best known algorithm to a factor of 2.

It was conjectured in \cite{Khovanova:Baron} that $B(n)$ is
very close to $\log_3 n$, a statement that can, perhaps, be rigorously taken
to mean that $B(n)$ is $\log_3 n + \o(\log_3 n)$. The main claim of this paper
is:

\begin{thm}\label{T:B}
The sequence $B(n)$ is $\log_3 n + \O(\log \log n)$.
\end{thm}

\subsection{The Baron's homogeneous omni-sequence}
All constructions in this paper (with the exception of constructions for
$n<4$, where these are impossible), belong to a special class of weigh-sets
we call \emph{homogeneous}.
A \emph{homogeneous weigh set} is a matrix, $M$, such that $M\vn=\vz$.
By definition, homogeneous \M weigh-sets require that $M\vn=\vz$ and that
$M\vec{v'}\neq\vz$ for $\vec{v'}$ that is a nontrivial permutation of $\vn$
(where by ``nontrivial permutation'' we mean any permutation other than the
identity). This definition does not involve any use of the sign function, and
therefore lends itself more easily to theoretical study. This may explain why
in previous papers regarding verification
\cite{Khovanova:Baron, Khovanova:Sequence, Brand:Tightening}
virtually all weigh-sets used are homogeneous.

We define \emph{The Baron's homogeneous omni-sequence} analogously to the
Baron's omni-sequence. For $n>3$, $B'(n)$ is
the smallest $m$ for which there exists an $m\times n$ homogeneous \M matrix.
This is also the smallest number of weighings required to verify the weights of
coins weighing $1,\ldots, n$ grams by use of balance scales that give only the
information of whether they balance or tip, but not to which direction they tip.

Because the weighing strategies described in this paper
are all homogeneous, we effectively also prove

\begin{thm}\label{T:B_prime}
The sequence $B'(n)$ is $\log_3 n + \O(\log \log n)$.
\end{thm}

We conjecture that $\Th(B(n)-\log_3 n)\equiv\Th(B'(n)-\log_3 n)$, implying that
the added information of the direction to which the scales tip (when they do)
is not a significant help in the \M problem.
 
\section{Special $n$ values}\label{S:special}
We begin by constructing \M matrices for some special $n$ values, noting that
these constructions are the first known constructions that give a
$\log_3 n+\o(\log n)$ bound on $B(n)$ for any infinite family of $n$ values.
For this, we introduce two new notions: monotonicity and balance.

\subsection{Monotonicity}
In \cite{Khovanova:Baron} and \cite{Brand:Tightening}, all constructions
iteratively establish partitions and then sub-partitions of the set
of $n$ coins. However, \cite{Khovanova:Baron} also cites solutions found by
computer searching, due to Konstantin Knop and Maxim Kalenkov, that
reveal that the optimal strategy (at least for the range
where computer searching is feasible) uses a different method. Consider, for
example, the following weigh-set for $n=19$, found by Maxim Kalenkov:
% {\footnotesize
\[M=\left(\begin{array}{ccccccccccccccccccc}
- & - & - & - & - & 0 & - & - & 0 & - & 0 & 0 & - & 0 & 0 & + & 0 & + & + \\
- & - & - & 0 & 0 & - & 0 & + & - & + & - & 0 & + & 0 & 0 & - & + & 0 & 0 \\
- & 0 & + & - & 0 & - & + & - & 0 & 0 & + & - & + & 0 & + & 0 & 0 & - & 0
\end{array}\right),\]
% }
where $+$ indicates $1$ and $-$ indicates $-1$. To demonstrate that this is a
\M matrix, consider the equation
% {\footnotesize
\[(12,7,3) M = (-22,-19,-16,-15,-12,-10,-9,-8,-7,-5,-4,-3,-2,0,3,5,7,9,12).\]
% }
The entries of the resulting vector form a strictly increasing list.

Formally, we define a \emph{monotone} matrix to be any matrix, $M$, for which
there exists a vector $\vec{w}$ such that the entries of the vector $\vec{w}M$
are monotone strictly increasing. The general claim is:

\begin{lem}\label{L:monotone}
Any homogeneous monotone matrix is a \M matrix.
\end{lem}

\begin{proof}
By definition of a homogeneous matrix, $M$ satisfies $M\vn=\vz$. Because $M$ is
monotone, we know that there exist vectors $\vec{w}$ and $\vec{c}$ such that
$\vec{w}M=\vec{c}$ and $\vec{c}$ has monotone strictly-increasing entries.
Therefore $\langle \vec{c}\cdot\vn \rangle=\vec{w}M\vn=0$. The rearrangement
inequality \cite{Hardy:Inequalities} states that the dot product of any two
vectors, $\vec{x}$ and $\vec{y}$, with strictly-increasing entries is strictly
larger than the dot product of $\vec{x}$ with any nontrivial permutation
of $\vec{y}$. In particular, for any nontrivial permutation $\vec{v'}$ of
$\vn$, $\langle \vec{c}\cdot\vec{v'} \rangle\neq 0$, so $M\vec{v'}\neq\vz$.
\end{proof}

\subsection{Balance}
A matrix $M$ is \emph{balanced} if $M\vu=\vz$.

Unlike monotonicity, which has roots in the works of Knop and Kalenkov,
the concept of balance is an innovation of this paper. Balance allows
``good'' constructions to be repeated for different $n$ values:
if $M$ is a balanced homogeneous $m \times n$ matrix, then $M\vec{v}=\vz$ not
only for $\vec{v}=\vn$, but also for any $\vec{v}$ that is a linear progression
of length $n$.
This allows us to create a new balanced homogeneous weighing $\{L',R'\}$ from
an existing balanced homogeneous weighing $\{L,R\}$, by setting
$L'=\{ax+b\colon x\in L\}$ and $R'=\{ax+b\colon x\in R\}$ for any integers
$a$ and $b$.

Furthermore, if $\{L_A,R_A\}$ and $\{L_B,R_B\}$ are two balanced homogeneous
weighings, then so are $\{L_A \uplus L_B, R_A \uplus R_B\}$, if
$L_A \uplus L_B$ and $R_A \uplus R_B$ (the disjoint unions) are well defined
and do not intersect.

For matrices $A$ and $B$, we use the standard block notation
$(\text{$A$ $B$})$ and
$\binom{A}{B}$ to indicate that $A$ and $B$ are placed side-by-side and
one on top of the other, respectively, in a new matrix. Additionally,
we denote by $(A \times k)$ and $[A \times k]$ the matrix defined by arranging
$k$ copies of $A$ side-by-side and that created by copying each column of $A$
$k$ times, respectively.
Otherwise stated: $(A \times k)\defeq \vu_k^T \otimes A$ and
$[A \times k]\defeq A \otimes \vu_k^T$, where $\otimes$ signifies the
Kronecker product.
In all operations described, vectors can be used as matrices.

These operations are useful, because if the operands are balanced homogeneous
weigh-sets, then so are the results.

Define the \emph{$t$-th moment} of a vector $\vec{v}$ to be $\sum_i v_i i^t$.
A vector is balanced if its $0$-th moment is $0$. It is homogeneous if its
first moment is $0$. We refer to the $0$-th moment as the $\emph{imbalance}$.
The first moment will simply be referred to as \emph{the moment}.

\subsection{The basic idea}
Clearly, both monotonicity and balance are desirable properties in constructing
homogeneous \M matrices. The following hypothetical construction demonstrates
the gist of how this is done.

\begin{construct}\label{L:monotone_strategy}
If $M$ is a homogeneous, monotone, balanced weigh-set of dimensions
$m \times n$, and $\{M_i\}_{i=1}^\infty$ is defined recursively as
$$M_1=M,$$
$$M_{i+1}=\binom{M \times n^i}{[M_i \times n]},$$
then for all $i$, $M_i$ is a homogeneous, monotone, balanced, \M weigh-set.
\end{construct}

\begin{proof}
It is clear that all $M_i$ are homogeneous and balanced. By
Lemma \ref{L:monotone}, if $M_i$ is homogeneous and monotone, it is also \M.
We therefore only need to prove that all $M_i$ are monotone.

Consider the vector $\vec{w}$ satisfying $\vec{w}M=\vec{c}$ with
a monotone strictly-increasing $\vec{c}$. Choose a number $C$, larger than
$\max(\vec{c})-\min(\vec{c})$. Define recursively the following vector sequence.
$$\vec{w}_1=\vec{w},$$
$$\vec{w}_{i+1}=(\text{$\vec{w}$ $C\vec{w}_i$}),$$
where $(\text{$\vec{a}$ $\vec{b}$})$ indicates that vector $\vec{b}$ is
appended to vector $\vec{a}$ and $C\vec{w}$ is scalar multiplication. The vector
$\vec{c}_k\defeq \vec{w}_kM_k$ has monotone
strictly-increasing entries. To see this, note that the result at column $j$ is
$\sum_{l=1}^{i} c_{r(l)} C^l$, where
$r(l)\equiv\lceil j/n^{l-1} \rceil \pmod n$.
One can formally view these sums over all
$j$ as an enumeration in base $C$ using the digits $c_1,\ldots, c_n$. The
enumeration clearly forms a strictly-increasing list.
\end{proof}

Unfortunately, as it stands, this construction is merely hypothetical because
the conditions required of $M$ are never satisfied.

\begin{lem}
No homogeneous, balanced weigh-set is monotone.
\end{lem}

\begin{proof}
If $M$ is a homogeneous, balanced weigh-set, then $M\vn=\vz$ and $M\vu=\vz$,
and therefore also $M(a\vn+b\vu)=\vz$ for any choice of $a$ and $b$.
In particular, choosing $a=-1$, $b=n+1$ we get $a\vn+b\vu=(n,\ldots,1)^T$,
which is a permutation on $\vn$. This means that there exists a nontrivial
permutation on $\vn$, $\vec{v'}$, that yields $M\vec{v'}=\vz$, so $M$ is not a
\M matrix. By Lemma \ref{L:monotone}, it is not monotone.
\end{proof}

We therefore augment our requirements to ``the next best thing''.
Let a weigh-set be \emph{$t$-part piecewise-monotone} if its columns can be
partitioned into at most $t$ consecutive parts, such that each part forms a
monotone weigh-set. A $t$-part piecewise-monotone weigh-set $M$ is
\emph{$k$-regular} if each monotone part in the column-partition of $M$ is
exactly $k$ columns wide. The qualifiers ``$t$-part'' and ``$k$-regular'' may
be omitted if they are understood from the context.

\begin{lem}\label{L:piecewise_strategy}
Let $M$ be a homogeneous, balanced, $k$-regular piecewise-monotone
weigh-set of dimensions $m \times kt$, and let
$\{M_i\}_{i=1}^\infty$ be a sequence of weigh-sets defined recursively as
$$M_1=M,$$
$$M_{i+1}=\binom{M \times k^i}{[M_i \times k]},$$
then for all $i$, $M_i$ is a homogeneous, balanced, $k^i$-regular $t$-part
piecewise-monotone weigh-set of dimensions $mi \times k^i t$.
\end{lem}

\begin{proof}
The proof is essentially the same as for
Hypothetical Construct \ref{L:monotone_strategy}.
\end{proof}

Our main theorem in this section is

\begin{thm}\label{T:incomplete}
For any $\alpha>1$ there exists a constant $C$ such that there exist
$m \times n$ homogeneous \M matrices with $m \le \alpha \log_3 n+C$ for
arbitrarily large values of $n$.
\end{thm}

The basis of the proof for Theorem \ref{T:incomplete} is
Lemma \ref{L:piecewise_strategy}. However, we still need to show that a
suitable matrix $M$ (as in Lemma \ref{L:piecewise_strategy}) can be provided,
and that the resulting
$t$-part piecewise-monotone weigh-sets can be made into homogeneous \M matrices.
The first part is discussed in Subsection \ref{SS:base}. The second part is
established by the following lemma.

\begin{lem}\label{L:completion}
Any homogeneous, $t$-part piecewise-monotone weigh-set can be extended
into a \M weigh-set by adding $\O(t)$ further weighings into the set.
\end{lem}

\begin{proof}
Each part of the piecewise-monotone weigh-set is individually monotone. By
the reasoning of
Lemma \ref{L:monotone}, the weigh-set is a verification subject to its
piecewise-monotone partition.
To complete the piecewise-monotone weigh-set into a
\M weigh-set, we add weighings that establish this partition.
What we need to prove is that $\O(t)$ additional weighings suffice.

We prove, more generally, that for $1\le j< n$ it is possible to separate
the coins $1,\ldots,j$ from the coins $j+1,\ldots,n$ in at most $8$ weighings.
Repeating this for each of the at-most $t-1$ partition separation points,
the full partition will have been established and the proof completed.

To separate the coins $1,\ldots,j$ from the coins $j+1,\ldots,n$, we consider
two cases:

\begin{description}
\item{Case 1: $2(j^2+j)\ge n^2+n$}

Let $x$ be the minimum integer such that
$x^2+x\ge (n^2+n)-(j^2+j)$.
\begin{description}
\item{Case 1a: $x^2+x=(n^2+n)-(j^2+j)$}

In this case, the set of coins $\{1,\ldots,x\}$ weighs the same as
$\{j+1,\ldots,n\}$. Balancing them against each other establishes the partition
$\{\{1,\ldots, x\},\{x+1,\ldots, j\},\{j+1,\ldots, n\}\}$, and, in particular,
the partition we have set out to establish.

This is true because replacing any of the coins $1,\ldots,x$ would have made
their pan heavier, whereas replacing any of the coins $j+1,\ldots,n$ would have
made their pan lighter.
\item{Case 1b: $x^2+x>(n^2+n)-(j^2+j)$}

In this case, weighing $L=\{1,\ldots,x\}$ against $R=\{j+1,\ldots,n\}$ would
have resulted in an imbalance of $y$, $1\le y<x$, in favor of the former.
Instead, as a first weighing we balance $L\setminus\{y\}$ against $R$.
To establish the partition, we must now merely
verify the identity of coin $y$. However, in \cite{Khovanova:Sequence} it was
already shown that at most $7$ weighings are necessary to verify the weight of
any single coin.
\end{description}
\item{Case 2: $2(j^2+j)< n^2+n$}

In this case, we can no longer use the
system described above, because there would be overlaps between $1,\ldots,x$ and
$j+1,\ldots,n$. Instead, we pick $x$ as the maximal value that satisfies
$x^2+x \le(n^2+n)-(j^2-j)$. Note the use of $j^2-j$, not $j^2+j$.
\begin{description}
\item{Case 2a: $x^2+x \ge (n^2+n)-(j^2+j)$}

Let $y=((j^2+j)+(x^2+x)-(n^2+n))/2$.
The value of $y$ lies in the range
$0\le y \le j$. The weight of $y$ can be verified in at most $7$ weighings,
following which balancing
$\{1,\ldots,j\}\setminus\{y\}$ against $\{x+1,\ldots,n\}$ establishes the
partition.
\item{Case 2b: $x^2+x<(n^2+n)-(j^2+j)$}

Balance $\{1,\ldots,j\}$ against $\{y,x+2,\ldots,n\}$, where $y$ is chosen to
satisfy equality of masses. The value of $y$ is in the range
$j+1 \le y \le x$, so the weighing is well-defined. We complete the
process, again, by verifying the weight of $y$ in at most $7$ additional
weighings.
\end{description}
\end{description}
\end{proof}

\subsection{Constructing a base matrix}\label{SS:base}
We now turn to the construction of the base matrix, $M$.

\begin{lem}\label{L:base}
For every $m\ge 2$, there is a $k$-regular piecewise-monotone, homogeneous,
balanced weigh-set of dimensions $m \times kt$, where $k> 3^{m-1}$
and $t\le 5k$.
\end{lem}

We remark that any bound on $t$ that is a polynomial in $k$ would have sufficed
to prove that $B'(n)$ is $\log_3 n+\O(\log \log n)$. We prove for a
low degree polynomial because it improves the constants used in the
$\O(\log \log n)$, but even so this bound is not tight.

\begin{proof}
We construct explicitly a matrix, $M$, satisfying the conditions
of the lemma.

Let $\vec{w}$ of length $m$ be defined by
\begin{equation*}
w_i=\begin{cases}
2\cdot 3^{m-1-i} & \text{if $i<m$,} \\
1 & \text{if $i=m$.}
\end{cases}
\end{equation*}
This will be the vector
satisfying that $\vec{c}=\vec{w}M$ is monotone
strictly-increasing in each $[ik+1,\ldots,(i+1)k]$ interval.

We choose $k$ to be the largest prime number less than
$2\cdot 3^{m-1}$. To satisfy the conditions of the lemma we require
that this value satisfies $3^{m-1}<k<2\cdot 3^{m-1}$, which is guaranteed by
Bertrand's postulate,
asserting the existence of a prime between $x$ and $2x$. We note that for
$m=2$ we have $k=5$, and that for $m>2$ both upper and lower bounds are
composite numbers. Hence, the inequalities are sharp in all cases.

Because $M$ is required to be homogeneous, we know that for each of its rows,
$M_{i*}$, we have $\langle M_{i*}\cdot\vn \rangle=\vz$. Because it is required
to be balanced, we have $\langle M_{i*}\cdot\vu \rangle=\vz$. Both of these
conditions are linear, so we know that they must also hold for $\vec{c}$. We
begin by designing such a vector.

Vector $\vec{c}$ will be several concatenated copies of a vector $\vec{c'}$
of length $k^2$. By choosing $\vec{c'}$ to be balanced and homogeneous,
$\vec{c}$ is also ensured to have these properties. Algorithm \ref{A:c_prime}
shows how to construct $\vec{c'}$.

% OLD PLACE FOR ALG

Each $[ik+1,\ldots,(i+1)k]$ interval in $\vec{c}$ is chosen by
Algorithm \ref{A:c_prime} to hold one of the
following possible lists of values, each of which is monotone
strictly-increasing: $(-(k+1)/2,\ldots,(k-3)/2)$,
$(-(k-1)/2,\ldots,(k-1)/2)$ or $(-(k-3)/2,\ldots,(k+1)/2)$, noting that $k$ is
a large prime and therefore odd. We call the first
``choice $-1$'', the second ``choice $0$'' and the third ``choice $+1$'',
according to the value of their associated $h'_{i+1}$. These
choices all satisfy the monotonicity requirement. By choosing the same number
of ``choice $-1$'' and ``choice $+1$'', balance (i.e.,
$\langle \vec{c} \cdot \vu \rangle=0$) is also guaranteed.

The remaining condition is homogeneity: $\langle \vec{c'} \cdot \vn \rangle=0$.
Let us consider the vector $\vec{\tilde{c}}$ that would have been returned by
Algorithm \ref{A:c_prime} had the ``while'' loop of step \ref{c_prime:while}
been stopped after fewer iterations than is required by the algorithm.

\begin{algorithm}[!h]
\caption{Finding the vector $\vec{c'}$ as a function of $k$}
\label{A:c_prime}
\begin{algorithmic}[1]
\STATE $\vec{h}' \gets \vz_k$
\STATE $T \gets (k-1)(k+1)/12$\label{c_prime:initialize}
\STATE $s \gets 1$
\STATE $f \gets k$
\WHILE{$T>0$}\label{c_prime:while}
\IF {$T<f-s$}
\STATE $f \gets T+s$
\ENDIF
\STATE $h'_s \gets 1$
\STATE $h'_f \gets -1$
\STATE $T \gets T-(f-s)$\label{c_prime:decrease}
\STATE $s \gets s+1$
\STATE $f \gets f-1$
\ENDWHILE
\FOR{$i \in 0,\ldots,k-1$}
\FOR{$j \in 0,\ldots,k-1$}
\STATE $c'_{ik+j+1} \gets -(k-1)/2+j+h'_{i+1}$
\ENDFOR
\ENDFOR
% \RETURN $(c'_1,\ldots,c'_{k^2})$
\STATE \textbf{return} $(c'_1,\ldots,c'_{k^2})$
\end{algorithmic}
\end{algorithm}

If terminated after $0$ iterations, $\vec{\tilde{c}}$ would have been the vector
with all ``choice $0$'' choices. Its moment,
$\langle \vec{\tilde{c}} \cdot \vn \rangle$, can be calculated as $2k P_{(k-1)/2}$,
where $P_r$ is the $r$'th square pyramidal number,
$$P_r=1^2+\cdots+r^2=r(r+1)(2r+1)/6,$$
because each $[ik+1,\ldots,(i+1)k]$ interval contributes $2 P_{(k-1)/2}$ to
the moment. This equals $k^2(k-1)(k+1)/12$.

At each iteration of the ``while'' loop, the moment is decreased by
incrementing by $1$ a list of $k$ consecutive values starting at position
$sk+1$, and decrementing by $1$ a list of $k$ consecutive values starting at
position $fk+1$. This decreases the moment by $k^2(f-s)$.

The value of $T$ in Algorithm $\ref{A:c_prime}$ is initialized at
step $\ref{c_prime:initialize}$ and decreased at $\ref{c_prime:decrease}$.
These updates of $T$ maintain the invariant
$\langle \vec{\tilde{c}} \cdot \vn \rangle=k^2 T$. Because we know that $T=0$ when
the ``while'' loop terminates, $\langle \vec{c'} \cdot \vn \rangle=0$, as
required.

To prove that the algorithm terminates, one can simply compute the number of
iterations required to cancel the initial moment. This
number is $\lceil k/2 - \sqrt{k^2/6+1/12} \rceil$. Not only does this prove
a successful termination of the algorithm, it also indicates that the middle
$\lfloor k\sqrt{2/3} \rfloor$ parts of $\vec{c'}$ have at most one non-``$0$''
choice.

Algorithm \ref{A:m_special} shows how to construct matrix $M$.

\begin{algorithm}[!h]
\caption{Finding $M$ as a function of $\vec{c'}$}
\label{A:m_special}
\begin{algorithmic}[1]
\STATE The vector $\vec{w}$ is as defined earlier.
\STATE $N'$ is a $0\times k^2$ matrix.
\STATE $N$ is a $0\times 0$ matrix.
\STATE $\vec{c} \gets \vz_0$
\STATE \COMMENT{\ensuremath{N'}, \ensuremath{N} and \ensuremath{\vec{c}}
initially contain no elements, but we use them as recursion bases.}
\FOR {$i \in 1,\ldots,m$}\label{m_special:i_loop}
\LOOP\label{m_special:endless_loop}
\STATE $\vec{c} \gets (\text{$\vec{c}$ $\vec{c'}$})$
\STATE $N \gets (\text{$N$ $N'$})$
\STATE $\mathit{len} \gets$ length of $\vec{c}$
\STATE $\vec{v} \gets \vz_\mathit{len}$
\STATE $\vec{r} \gets \vec{c}-\sum_{l=1}^{i-1} w_l N_{l*}$
\FOR {$R\subseteq \{j\colon r_j=3^{m-i-1}\}$ and $L\subseteq
\{j\colon r_j=-3^{m-i-1}\}$ subject to $|R|=|L|$}\label{m_special:rl_loop}
\FOR {$j \in 1,\ldots,\mathit{len}$}\label{m_special:v_assignment}
\IF {$j \in R$ or $r_j>3^{m-i-1}$}
\STATE $v_j \gets 1$
\ELSIF {$j \in L$ or $r_j<-3^{m-i-1}$}
\STATE $v_j \gets -1$
\ELSE
\STATE $v_j \gets 0$
\ENDIF
\ENDFOR
\IF {$\langle v \cdot \vn\rangle=0$}\label{m_special:breakpoint}
\STATE \textbf{go to \ref{m_special:success}}
\ENDIF
\ENDFOR
\ENDLOOP
\STATE $N' \gets \binom{N}{\vec{v}}$\label{m_special:success}
\STATE $\vec{c'} \gets \vec{c}$
\STATE $N$ is an $i\times 0$ matrix.
\STATE $\vec{c} \gets \vz_0$
\ENDFOR
\STATE $M \gets N'$
% \RETURN $M$
\STATE \textbf{return} $M$
\end{algorithmic}
\end{algorithm}

By construction, when Algorithm \ref{A:m_special} terminates, its output is
a $k$-regular piecewise-monotone, homogeneous,
balanced weigh-set of dimensions $m \times kt$, where $k> 3^{m-1}$.

To see this, note that Algorithm \ref{A:m_special} maintains as an invariant
throughout its execution that the absolute value of any element of $\vec{r}$
is at most $3^{m-i}$. At the termination of the loop at
step \ref{m_special:i_loop}, $\vec{r}$, which at this time computes
$\vec{c}-\vec{w}M$, will have become $\vz$. The equation $\vec{w}M=\vec{c}$
ensures all required monotonicity requirements. Homogeneity is ensured
explicitly at step \ref{m_special:breakpoint} and balance is a result of
the invariant maintained throughout that the number of appearances of any
value, $x$, in $\vec{r}$ is the same as the number of appearances of $-x$.
Under this invariant, the choice $|R|=|L|$ both ensures that each $\vec{v}$
tried in step \ref{m_special:breakpoint} is balanced and ascertains that the
invariant is retained in all future steps.

In order to complete the proof of the lemma, what still needs proving is that
the algorithm terminates at all, and that it terminates
with a sufficiently low $t$. We begin by proving termination.

The question of Algorithm \ref{A:m_special}'s termination is the question of
whether suitable $R$ and $L$ are always eventually found in the for-loop of
step \ref{m_special:rl_loop} that will allow escape from the endless loop of
step \ref{m_special:endless_loop} by satisfying the condition of
step \ref{m_special:breakpoint}.

We separate here two cases: $i=m$ and $i \neq m$. At the last iteration of the
main for-loop (step \ref{m_special:i_loop}), the condition of
step \ref{m_special:breakpoint} is met immediately in the first pass through
the loop of step \ref{m_special:endless_loop} and using the only choices for
$R$ and $L$ possible in the for loop of step \ref{m_special:rl_loop}, namely
$R=L=\emptyset$.

The reason for this is that, as previously noted, Algorithm \ref{A:m_special}
maintains as an invariant
throughout its execution that the absolute value of any element of $\vec{r}$
is at most $3^{m-i}$. At $i=m$, $\vec{r}$ is therefore a
$\{-1,0,1\}$-vector, so at the for-loop of step \ref{m_special:v_assignment},
$\vec{v}$ is chosen to be $\vec{r}$, reducing $\vec{w} M - \vec{c}$ to zero.
(Throughout the process, $\vec{r}$ keeps a tally of this difference.)
By construction
$\langle \vec{c} \cdot \vn \rangle=0$, and also each row of $M$ other than the
last is homogeneous. By linearity, we conclude that the last row of $M$ must
also be homogeneous.

For the case $i<m$, let us consider a variation on Algorithm \ref{A:m_special},
where the comprehensive search over all possible $R$ and $L$ combinations
presented in step \ref{m_special:rl_loop} is replaced by a much more efficient,
though possibly sub-optimal, search. This change definitely cannot make
Algorithm \ref{A:m_special} terminate if it had otherwise not terminated, nor
can it decrease the value of $t$ at termination.

The simpler method to come up with $(R,L)$ pairs is divided into three stages.
First, we initialize $\vec{v}$.
In a second step, we reduce the moment of $\vec{v}$ to almost zero.
(Specifically, at the end of the process its absolute value is less than
$2k$.) Finally, we zero the moment out completely.

We describe the process here as an algorithm that
chooses $\vec{v}$ directly, not going through the process of picking out
$R$ and $L$ first. The initialization is described in
Algorithm \ref{A:initialize}. The rough correction stage is described in
Algorithm \ref{A:rough}. The fine correction stage is then described in
Algorithm \ref{A:fine}.

Let $\vec{v^0}$ be the value returned by Algorithm \ref{A:initialize}.

\begin{algorithm}[!h]
\caption{Initializing $\vec{v}$}
\label{A:initialize}
\begin{algorithmic}[1]
\FOR {$j \in 1,\ldots,s$}
\IF {$r_j>3^{m-i-1}$}
\STATE $v_j \gets 1$
\ELSIF {$r_j<-3^{m-i-1}$}
\STATE $v_j \gets -1$
\ELSE
\STATE $v_j \gets 0$
\ENDIF
\ENDFOR
% \RETURN $\vec{v}$
\STATE \textbf{return} $\vec{v}$
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[!h]
\caption{Rough correction of moment}
\label{A:rough}
% \footnotesize
\begin{algorithmic}[1]
\STATE $\mathit{moment} \gets \langle \vec{v} \cdot \vn \rangle$
\STATE $\mathit{pos} \gets 2 \cdot 3^{m-i-1}$
\STATE $\mathit{neg} \gets k-\mathit{pos}$
\IF {$pos<neg$}
\STATE $\mathit{target} \gets \{0,\ldots,2k-1\}$
\ELSE
\STATE $\mathit{target} \gets \{1-2k,\ldots,0\}$
\ENDIF
\WHILE {$\mathit{moment} \notin \mathit{target}$}
\STATE $\mathit{pvals} \gets \{l\colon \text{$r_l=3^{m-i-1}$ and $v_l=0$}\}$
\STATE $\mathit{nvals} \gets \{l\colon \text{$r_l=-3^{m-i-1}$ and $v_l=0$}\}$
\IF {$\mathit{pvals}=\emptyset$}
\STATE \COMMENT{Failed to correct the moment.}
\STATE \textbf{quit}\label{rough:fail}
\ENDIF
\IF {$\mathit{moment}>0$}
\STATE $s \gets \min(\mathit{pvals})$
\STATE $f \gets \max(\mathit{nvals})$
\STATE $x \gets \min(\mathit{nvals})$
\WHILE {$\mathit{moment}-(x-s)>\max(\mathit{target})$ and $x\neq f$}
\STATE $\mathit{nvals} \gets \mathit{nvals}\setminus\{x\}$
\STATE $x \gets \min(\mathit{nvals})$
\ENDWHILE
\STATE $v_s \gets 1$
\STATE $v_x \gets -1$
\STATE $\mathit{moment} \gets \mathit{moment}-(x-s)$
% \algstore{AS:rough}
% \end{algorithmic}
% \end{algorithm}
% 
% \begin{algorithm}
% \begin{algorithmic}[1]
% \algrestore{AS:rough}
\ELSE
\STATE $s \gets \min(\mathit{nvals})$
\STATE $f \gets \max(\mathit{pvals})$
\STATE $x \gets \min(\mathit{pvals})$
\WHILE {$\mathit{moment}-(s-x)<\min(\mathit{target})$ and $x\neq f$}
\STATE $\mathit{pvals} \gets \mathit{pvals}\setminus\{x\}$
\STATE $x \gets \min(\mathit{pvals})$
\ENDWHILE
\STATE $v_s \gets -1$
\STATE $v_x \gets 1$
\STATE $\mathit{moment} \gets \mathit{moment}-(s-x)$
\ENDIF
\ENDWHILE
% \RETURN $\vec{v}$
\STATE \textbf{return} $\vec{v}$
\end{algorithmic}
\end{algorithm}

Algorithm \ref{A:rough} attempts to cancel out the moment of $\vec{v^0}$ by a
method similar to that used in Algorithm \ref{A:c_prime} for the generation of
$\vec{c'}$. Set $R$ is assigned the lowest possible values, and set $L$ is
assigned the highest ones, subject to not overshooting the moment's
target zone. Though it may be that $|R|$ and $|L|$ cannot be made large enough
to counter all existing moment, in which case the algorithm will fail,
reaching step \ref{rough:fail}, the one thing ensured by the algorithm is that
it will not overshoot the mark: because there is a value that can be added to
$L$ at every interval of length $k$, the moment is decreased by at most
$2k$ at every step, ensuring that the target zone is not missed.

Though this algorithm may not be able to cancel out the initial moment,
repeatedly
appending copies of this basic $\vec{v}$ to each other (which is what is done
by the loop in step \ref{m_special:endless_loop} of Algorithm \ref{A:m_special})
is sure to eventually result in a vector for which this Algorithm \ref{A:rough}
terminates successfully. Suppose that
the vector's original length was $kl$ and that it was appended to itself $r$
times. If the initial moment was $b$, after $r$ repetitions it has become
$rb$. However, because there is a candidate for
$R$ and a candidate for $L$ in every interval of length $k$,
Algorithm \ref{A:rough} is sure to be able to cancel out a moment of
order $\O(kr^2l^2)$. For a large-enough $r$, the moment-countering ability,
growing as a quadratic function of $r$, will
suffice to cancel the moment, which grows as a linear function of $r$, and the
algorithm will terminate successfully.

Furthermore, by appending yet additional copies of the initial $\vec{v}$,
countering the moment generated by $r$ copies will require the cardinalities of
$R$ and $L$ (which are equal) to be
$\O(\sqrt{r})$. This means
that in increasing $r$ we also increase, without bound, the number of intervals
that are unused by both $R$ and $L$, and are therefore free to be used by
Algorithm \ref{A:fine}.

We now move to analyzing the fine-tuning algorithm. We prove that given enough
``free'' intervals (as guaranteed, given a large enough $r$), the fine-tuning
algorithm terminates successfully.
Algorithm \ref{A:fine} describes the fine-tuning algorithm for the case
$\mathit{moment}>0$.
The case $\mathit{moment}<0$ is symmetric, with the roles of negatives
and positives reversed. (And the case $\mathit{moment}=0$ requires no
further moment-cancellation, of course.)

\begin{algorithm}[!h]
\caption{Fine correction of the moment}
\label{A:fine}
\begin{algorithmic}[1]
\REQUIRE $\mathit{moment}>0$
\STATE $\mathit{pvals} \gets \{l\colon \text{$r_l=3^{m-i-1}$ and $v_l=0$}\}$
\STATE $\mathit{nvals} \gets \{l\colon \text{$r_l=-3^{m-i-1}$ and $v_l=0$}\}$
\STATE $\mathit{nump} \gets$ minimum nonnegative integer such that
$\mathit{neg}|\mathit{moment}+\mathit{nump}\cdot\mathit{pos}$\label{fine:set_nump}
\STATE $\mathit{numn} \gets
(\mathit{moment}+\mathit{nump}\cdot\mathit{pos})/\mathit{neg}$
\STATE $\mathit{pairs} \gets
\{l\colon \text{$l\in\mathit{pvals}$ and $l-\mathit{pos}\in\mathit{nvals}$}\}$
\IF {$|\mathit{pairs}|<\mathit{nump}$}
\STATE \COMMENT{Failed to correct the moment.}
\STATE \textbf{quit}
\ENDIF
\FOR {$l \in$ $\mathit{nump}$ lowest elements of $\mathit{pairs}$}
\STATE $v_l \gets 1$
\STATE $v_{l-\mathit{pos}} \gets -1$
\ENDFOR
\STATE $\mathit{pvals} \gets \{l\colon \text{$r_l=3^{m-i-1}$ and $v_l=0$}\}$
\STATE $\mathit{nvals} \gets \{l\colon \text{$r_l=-3^{m-i-1}$ and $v_l=0$}\}$
\STATE $\mathit{pairs} \gets
\{l\colon \text{$l\in\mathit{pvals}$ and $l+\mathit{neg}\in\mathit{nvals}$}\}$
\IF {$|\mathit{pairs}|<\mathit{numn}$}
\STATE \COMMENT{Failed to correct the moment.}
\STATE \textbf{quit}
\ENDIF
\FOR {$l \in$ $\mathit{numn}$ lowest elements of $\mathit{pairs}$}
\STATE $v_l \gets 1$
\STATE $v_{l+\mathit{neg}} \gets -1$
\ENDFOR
% \RETURN $\vec{v}$
\STATE \textbf{return} $\vec{v}$
\end{algorithmic}
\end{algorithm}

The way that Algorithm \ref{A:fine} works is by seeking pairs of potential
values for $R$ and for $L$, $(r,l)$, such that $l-r=\mathit{pos}$ and such
that $r-l=\mathit{neg}$. It then uses the minimal amount of each type of pair
needed in order to cancel out the remaining moment. Because we chose $k$
to be prime, $\mathit{pos}$ and $\mathit{neg}$, satisfying
$\mathit{pos}+\mathit{neg}=k$, are necessarily co-prime. Therefore, there is
necessarily some $\mathit{nump}<\mathit{neg}$ that satisfies
$\mathit{neg}|(\mathit{moment}+\mathit{nump}\cdot\mathit{pos})$. The number
of $\mathit{neg}$ needed, $\mathit{numn}$ is then bounded by
$\mathit{nump}\cdot\mathit{pos}/\mathit{neg} + \mathit{moment}/\mathit{neg}$,
where the first part is bounded by $\mathit{pos}$ and the second part by $4$,
because it is known that $\mathit{neg}>\mathit{pos}$, and therefore
$\mathit{neg}>k/2$, whereas $\mathit{moment}<2k$.

We now need to ensure that enough pairs with differences $\mathit{pos}$ and
$\mathit{neg}$ exist. By the construction of $\vec{c}$, a pair with a
difference of
$\mathit{pos}$ exists in every $[ik+1,\ldots,(i+1)k]$ interval not used by the
rough-cancellation step. To obtain a
difference of $\mathit{neg}$, we need two such consecutive intervals with the
same ``choice''. Note, however, that in $\vec{c'}$ there are at most $5$ cases
where consecutive ``choice''s are different (when considering $\vec{c'}$ as
cyclic, which is how it is used in constructing $\vec{c}$).

Because the fine-tuning algorithm is not guaranteed to be able to use
any interval already utilized at the rough-cancellation step, consider the
situation of the used intervals at the end of that previous step.
The rough-cancellation algorithm uses the intervals of $\vec{v}$ corresponding
to the lowest and highest valued elements of $\vn$, but it leaves in the middle
one consecutive portion of unused intervals, with at most one used interval
interrupting it.

We claim that if this consecutive portion is of length $2k+13$ intervals or
more, this
guarantees that the fine-tuning algorithm will terminate successfully.
The case that requires the greatest number of intervals for the fine-tuning
step is $\mathit{pos}=k-1$, $\mathit{neg}=1$, with the original moment
being $2k-1$. This requires $k-2$ $\mathit{neg}$-pairs (each of which requires
$2$ intervals) and $3$ $\mathit{pos}$-pairs (each of which requires a single
interval), for a total of $2k-1$ intervals. Given that in any consecutive set of
at most $3k$ intervals there cannot be more than $15$ ``choice'' changes, and
in each such ``choice'' change there is at most one interval that cannot be
used to create a $\mathit{neg}$-sized interval, the total number of intervals
needed can be bounded by the following computation:
$2k-4$ (number of intervals used in
$\mathit{neg}$ pairs) $+15$ (number of intervals wasted over ``choice''
changes) $+2$ (number of intervals wasted because they or the interval after
them was used in the rough-cancellation stage) $=2k+13$. We note that in this
worst-case scenario there is no need to add $3$ more intervals for the
$\mathit{pos}$ pairs, as the $\mathit{pos}$ pairs can use any of the $15$
intervals unusable by $\mathit{neg}$ pairs due to ``choice'' changes.

For large enough $m$ we have $2k+13\le 3k$, so the argument holds. The only
$m$ for which this does not hold is $m=2$. We now show that for $m\ge4$,
$\vec{c}=(\vec{c'}\times5)$ suffices for
Algorithm \ref{A:rough} to leave this many unused intervals, ensuring the
successful termination of Algorithm \ref{A:m_special} with matrix dimensions
meeting the condition $t\le5k$ of the lemma. We treat the case $m<4$ separately.

First, let us consider the size of the moment that needs to be
counteracted at each step. Our original $\vec{c'}$, of length $k^2$, was
composed of $k$ repetitions of either $-(k-1)/2,\ldots, (k-1)/2$ or
$-(k-3)/2,\ldots, (k-3)/2$, and also at most
$(k-1)/2$ pairs of $-(k+1)/2$ and $(k+1)/2$, values that appear, in total, at
most once per $k$-length interval.

Consider the repetitions of $-(k-1)/2,\ldots, (k-1)/2$
or $-(k-3)/2,\ldots, (k-3)/2$ in $\vec{c}$. Each such repetition includes one
$-x$ for every $x$. As a result, $\vec{v^0}$, taken over the same indices, is
balanced. The greatest moment that can occur in such
a segment is $(k^2-1)/4$, for a total of $(k^2-1)/4\cdot k=(k^3-k)/4$
per repetition of $\vec{c'}$.
The remaining $(-(k+1)/2,(k+1)/2)$ and $(-(k-1)/2,(k-1)/2)$ value pairs also
result in a balanced set. Consider their moment. This moment is the
result of ``choice $-1$'' and ``choice $+1$'' pairs taken at the $\vec{c'}$
determination stage. In designing $\vec{c'}$ we needed to cancel out a
moment of $(k-1)k^2(k+1)/12$. For this, we chose $(s,f)$ pairs, and made
the $s$-interval into a ``choice $+1$'' and the $f$-interval into a
``choice $-1$''.
This cancels out exactly $(f-s)k^2$. In terms of $\vec{v^0}$, such a move
creates, at most, $2(f-s+1)k$ of moment. Knowing that the sum of all $f-s$ is
$(k-1)(k+1)/12$, the total is bounded by $(k-1)k(k+1)/6+2pk$, where $p$ is
the number of pairs used, which cannot be larger than $(k-1)/2$. Adding all
this together and multiplying by $5$, because the claim is that $\vec{c}$ has
at most $5$ repetitions of
$\vec{c'}$, we get $\tfrac{25}{12}k^3+5k^2-\tfrac{85}{12}k$.
The total moment for $\vec{v^0}$ at step $i=1$ of
Algorithm \ref{A:m_special} is therefore bounded by
$\tfrac{25}{12}k^3+5k^2-\tfrac{85}{12}k$.

The choice of $(R,L)$ at $i=1$ must therefore create a $\vec{v}$ with at most
this moment, because the two moments must cancel each other exactly. Let us
call the moment created by the choice of $(R,L)$ at iteration $i$ by the
name $b_i$. We have $b_1\le \tfrac{25}{12}k^3+5k^2-\tfrac{85}{12}k$.

In subsequent steps, however, the moment can be significantly higher. The
reason for this is that the values of $\vec{v^0}$ in all subsequent steps are
reversed by the choice of $(R,L)$ at all indices in $R\cup L$.
(A value of $3^i$ can be
described in one of two ways. It is either $\sum_{j=m-i}^{m} w_j$ or
$w_{m-i-1}-\sum_{j=m-i}^{m} w_j$. Adding a position to $R$ adds $w_{m-i-1}$ to
the equation, and therefore reverses all subsequent choices.) This adds a
further $2b_1$ to the moment that needs to be corrected by $b_2$, so
$|b_2|\le 3b_1$. In total, we have the equation
$|b_i|\le \left(\tfrac{25}{12}k^3+5k^2-\tfrac{85}{12}k\right) 3^{i-1}$.

On the other hand, consider how much moment can be countered at each step. In
$\vec{c}$, every $k$-sized interval includes all numbers from $-(k-3)/2$ to
$(k-3)/2$, and among them all the numbers from $-(3^{m-1}-1)/2$ to
$(3^{m-1}-1)/2$, being a total
of $3^{m-1}$ consecutive numbers. At iteration $i$ of
Algorithm \ref{A:m_special},
the candidates for $R$ are exactly those positions whose $c_j$ is congruent
to $3^{m-i-1} \pmod {2\cdot 3^{m-i}}$ and the candidates for $L$ are exactly
those positions whose $c_j$ is congruent to
$-3^{m-i-1} \pmod {2\cdot 3^{m-i}}$.
(Only $w_m$ is odd. All other $w_i$ are even. However, $w_1/2,\ldots,w_{m-1}/2$
form the powers of $3$, and it is well known that any integer can be
expressed uniquely in base $3$ using the digits $\{-1,0,1\}$. Therefore, every
odd number in the range can be expressed by exactly $2$ combinations of $w_i$,
depending on whether $w_m$ is added or subtracted. The numbers that are
potentials for $R$ in iteration $i$ of Algorithm \ref{A:m_special} are exactly
those $2x+1$ for which $x$ has a $0$ in its $i$'th digit in $\{-1,0,1\}$
base-$3$ representation and $x+1$ has a $1$. Similarly, candidates for $L$ are
those where $x$ has a $-1$ and $x+1$ has a $0$.)

Careful accounting shows that the number of candidates for $R$ in every
interval of length $k$ is $(3^{i-1}+1)/2$. This is given by the
following computation.
We have $(3^{i-1}-1)/2$ due to this many full sets
of all residues modulo $2\cdot 3^{m-i}$. In addition, we have one more
candidate due to the fact that remaining $\vec{c}$ entries include all
residues in the range
$0,\ldots, (3^{m-i}-1)/2$, and so, in particular, they also include
one that is congruent to $3^{m-i-1} \pmod {2\cdot 3^{m-i}}$.
The total, $(3^{i-1}+1)/2$, is also the number of candidates for
$L$.

Suppose that all candidates in the first $(3k-13)/2$ intervals were placed in
set $R$ and all candidates in the last $(3k-13)/2$ intervals were placed in set
$L$. This would still leave $2k+13$ free intervals, which we know is enough for
fine tuning. To see how much moment can be corrected by this choice, note
that we can pair each member $r$ of $R$ with a member $l$ of $L$ that is exactly
$(7k+13)/2$ intervals away from it. Even if $l$ and $r$ are at their closest
positions within their respective intervals, this is still a difference of
$(7k^2+11k)/2$. The total correctable moment is bounded from below by the
product of this difference and the number of candidates used,
$(3^{i-1}+1)/2\cdot(3k-13)/2$. The product is
$(3^{i-1}+1)(\tfrac{21}{8}k^3-\tfrac{29}{4}k^2-\tfrac{143}{8}k)$, which is more
than $3^{i-1}(\tfrac{21}{8}k^3-\tfrac{29}{4}k^2-\tfrac{143}{8}k)$.
The algorithm succeeds if this is enough to counterbalance an initial
moment of $b_i$, which is bounded from above by
$\left(\tfrac{25}{12}k^3+5k^2-\tfrac{85}{12}k\right) 3^{i-1}$.

Success of the algorithm depends, therefore, on the correctness of the
inequality
$$\frac{25}{12}k^3+5k^2-\frac{85}{12}k \le
\frac{21}{8}k^3-\frac{29}{4}k^2-\frac{143}{8}k,$$
or, equivalently, $13k^2-294k-259\ge0$.
This is true for $k\ge24$, so in particular for the $k$ values chosen for
any $m\ge4$.

We have shown that for $m\ge4$, if the width of the matrices of
Algorithm \ref{A:m_special}
ever reaches $5k^2$ (being $5$ times the width at the start of the algorithm)
the loop of step \ref{m_special:endless_loop} will always be stopped at its
very first iteration at step \ref{m_special:breakpoint}. The width
will not increase beyond this point. We can therefore tweak
Algorithm \ref{A:m_special} to begin by choosing
$\vec{c}=(\vec{c'} \times 5)$, thereby ensuring that this will also be the
final width.

Algorithm \ref{A:m_special_final} summarizes this final algorithm.

\begin{algorithm}[!h]
\caption{Finding $M$, final}
\label{A:m_special_final}
\begin{algorithmic}[1]
\STATE Find $\vec{c'}$ as in Algorithm \ref{A:c_prime}.
\STATE $\vec{c} \gets (\vec{c'} \times 5)$
\STATE $\mathit{len} \gets 5k^2$
\STATE $M \gets \mz_{m\times \mathit{len}}$
\STATE $\vec{w} \gets (2\cdot 3^{m-2},\ldots,2,1)$.
\FOR {$i \in 1,\ldots,m$}
\STATE $\vec{v} \gets \vz_\mathit{len}$
\STATE $\vec{r} \gets \vec{c}-\sum_{l=1}^{i-1} w_l M_{l*}$
\STATE Initialize $\vec{v}$ as in Algorithm \ref{A:initialize}
\STATE Update $\vec{v}$ as in Algorithm \ref{A:rough}.\label{m_special_final:rough}
\IF{$\mathit{moment}>0$}
\STATE Update $\vec{v}$ as in Algorithm \ref{A:fine}.
\ELSIF{$\mathit{moment}<0$}
\STATE Update $\vec{v}$ as in Algorithm \ref{A:fine}, with positives and
negatives reversed.
\ENDIF
\STATE $M_{i*} \gets \vec{v}$
\ENDFOR
% \RETURN $M$
\STATE \textbf{return} $M$
\end{algorithmic}
\end{algorithm}

Algorithm \ref{A:m_special_final} is guaranteed to work for $m\ge4$. However,
by simply running it on a computer it was possible to ascertain that it
terminates successfully also in the cases $m\in\{2,3\}$. Therefore, the
lemma is proved for all $m\ge2$.
\end{proof}

We can now complete the proof of this section's main claim, as follows.

\begin{proof}[Proof of Theorem \ref{T:incomplete}]
Let $M$ be any $k$-regular piecewise-monotone, homogeneous, balanced
weigh-set of dimensions $m \times kt$, then the sequence $\{M_i\}_{i=1}^\infty$
defined by Lemma \ref{L:piecewise_strategy} is a sequence of $t$-part
piecewise-monotone weigh-sets with
dimensions $m_i=mi$ and $n_i=k^i t$, being
arbitrarily large dimensions.

By Lemma \ref{L:completion}, adding $\O(t)$ further weighings
to these weigh-sets is enough to make them \M. This is a number independent of
$n$. We therefore have \M weigh-sets of dimensions $m'_i \times n_i$ equal to
$(mi+\O(t)) \times (k^i t)$.
These all satisfy $m'_i \le \alpha \log_3 n_i+C$ with $\alpha=m/\log_3 k$.

All that is left is to prove that $m/\log_3 k$ can be made arbitrarily close to
$1$. However, recall that in Lemma \ref{L:base} $M$ was constructed with
$k> 3^{m-1}$, meaning that $\alpha<m / (m-1)$, which can be made
arbitrarily close to $1$.
\end{proof}

Though not necessary for the main proofs of the
paper, it is still interesting to note that Theorem \ref{T:incomplete}
immediately implies the following.

\begin{cor}\label{T:little_o}
There exists a sequence $n$ values for which $B(n)$ is
$\log_3 n+\o(\log n)$.
\end{cor}

\section{General $n$ values}\label{S:general}

We now turn to the question of arbitrary $n$ values. Dealing with these
requires strengthening the tools built in Section \ref{S:special}.

Let $\mathcal{M}(m,k,t,n)$ be the set of homogeneous, $m\times n$
matrices (weigh-sets), such that $M\in \mathcal{M}(m,k,t,n)$ if and only if
there exists a vector $\vec{w}$ of length $m$, such that $\vec{c}=\vec{w}M$
satisfies the following properties:
\begin{align*}
c_i\le c_{i+1}&\quad (i\not\equiv n \pmod t),\\
c_i<c_{i+1}&\quad (\text{$i\equiv n \pmod t$ but $i\not\equiv n \pmod{kt}$}).
\end{align*}

This definition of $\mathcal{M}(m,k,t,n)$ is a generalization of monotonicity.
If $M$ is a $k$-regular $t$-part piecewise monotone, homogeneous
matrix, then $M \in \mathcal{M}(m,k,1,kt)$. Furthermore,
$[M\times r]$ is in $\mathcal{M}(m,k,r,rkt)$ and
$([M\times r]\times s)$ is in $\mathcal{M}(m,k,r,rkts)$.
In Section \ref{S:special}, we
proved that by joining $\mathcal{M}(m,k,k^i,k^rt)$ weigh-sets for
$i=0,\ldots,r-1$, one can construct a \M weigh-set of dimensions
$(mr+\O(t)) \times k^rt$. In this section, we use the more generalized form in
order to replace $k^rt$ by a general $n$.

However, before this can be done, we must first prove that the sets we use
are nonempty.

\begin{lem}\label{L:gen_base}
For every $m\ge 3$ and any positive $t$, there exist a
$k> 3^{m-1}$, such that $\mathcal{M}(m,k,t,n)$ is nonempty for
$n\ge 5tk^2$.
\end{lem}

\begin{proof}
The proof for Lemma \ref{L:gen_base} follows the general outline of the
construction in the proof for Lemma \ref{L:base}. We begin by choosing the
same $\vec{w}$ and $k$ as before, construct a suitable $\vec{c}$, and then
build a matrix $M \in \mathcal{M}(m,k,t,n)$ row by row.

The final algorithm used will follow the framework of
Algorithm \ref{A:m_special_final}. As is done there, the length of $\vec{c}$
here is known in advance. In our case, it is $n$. In this case, there is no
need to first construct $\vec{c'}$ and then duplicate it, as was done in
Algorithm \ref{A:m_special}. Instead, we construct $\vec{c}$ directly.
The process for doing so is similar to that described in
Algorithm \ref{A:c_prime}. However, three complications need to be accounted
for:
\begin{enumerate}
\item The matrix width, $n$, may not be a multiple of $kt$.
For this reason, a construction that duplicates
a basic construction of any width is not possible. In the construction used
here we will follow Algorithm \ref{A:c_prime} for the last
$\left\lfloor n / kt \right\rfloor kt$ columns, and will have special
handling for the first $n \bmod kt$ ones.
\item The moment that needs to be counterbalanced in
Algorithm \ref{A:c_prime} is known to be a multiple of $k^2$ (the equivalent of
which in this algorithm would be a multiple of $k^2t^2$), and can therefore
be tackled by ``choice $+1$'' and ``choice $-1$'' pairs. Here, the initial
moment is general. We handle this by first reducing the moment from its
original value, $I$, to $I \bmod k^2t^2$, as was done before. Next, we use
Lagrange's four-square theorem \cite{Ireland:number_theory} to represent the
remainder as a sum of $4$ squares (each of which is necessarily smaller than
$k^2t^2$). A moment of $a^2$, for $a\le kt$, can be created by shifting by
$1$ the $a$ highest values in one $kt$-length interval, and by $-1$ the lowest
values in the $kt$-length interval immediately following it.
\end{enumerate}

The new algorithm for choosing $\vec{c}$ is presented as
Algorithm \ref{A:gen_c}.

\begin{algorithm}[!h]
\caption{Finding the vector $\vec{c}$ as a function of $k$, $t$ and $n$}
\label{A:gen_c}
\begin{algorithmic}[1]
\STATE $b \gets \left\lfloor n / kt \right\rfloor$
\STATE $\vec{c} \gets \vz_n$
\STATE \COMMENT{Choosing the last $bkt$ elements of $\vec{c}$.}
\FOR{$i \in 0,\ldots,b-1$}
\FOR{$j \in 0,\ldots,k-1$}
\FOR{$r \in 1,\ldots,t$}
\STATE $c_{n-bkt+ikt+jt+r} \gets -(k-1)/2+j$
\ENDFOR
\ENDFOR
\ENDFOR
\STATE \COMMENT{Choosing the remaining elements of $\vec{c}$.}
\STATE $\mathit{rem} \gets n-bkt$
\STATE $\mathit{offset} \gets \left\lfloor \mathit{rem} / 2t \right\rfloor$
\STATE $\mathit{parity} \gets 1-\left(\left\lfloor \mathit{rem}/t \right\rfloor \mod 2\right)$
\FOR{$j \in 0,\ldots,(\mathit{offset}\times t)-1$}
\STATE $c_{n-bkt-j} \gets \mathit{offset}-\lfloor j/t \rfloor$
\ENDFOR
\FOR{$j \in \mathit{offset}\times t,\ldots, \mathit{rem}-1$}
\STATE $c_{n-bkt-j} \gets \mathit{offset}-\lfloor j/t \rfloor-\mathit{parity}$
\ENDFOR
\STATE \COMMENT{Rough moment cancellation.}
\STATE $\vec{h} \gets \vz_b$
\STATE $\mathit{moment} \gets \sum_{i=1}^{n} c_i i$
\STATE $s \gets 1$
\STATE $f \gets b$
\WHILE{$\mathit{moment}\ge k^2t^2$}\label{gen_c:rough}
\IF {$\mathit{moment}<(f-s)k^2t^2$}\label{gen_c:last}
\STATE $f \gets \left\lfloor\mathit{moment} / k^2t^2\right\rfloor+s$
\ENDIF
\STATE $h_s \gets 1$
\STATE $h_f \gets -1$
\STATE $\mathit{moment} \gets \mathit{moment}-(f-s)k^2t^2$
\STATE $s \gets s+1$
\STATE $f \gets f-1$
\ENDWHILE
\algstore{AS:gen_c}
\end{algorithmic}
\end{algorithm}

\begin{algorithm}[!h]
\begin{algorithmic}[1]
\algrestore{AS:gen_c}
\FOR{$i \in 0,\ldots,b-1$}
\FOR{$j \in 1,\ldots,kt$}
\STATE $c_{n-bkt+ikt+j} \gets c_{n-bkt+ikt+j}+h_{i+1}$
\ENDFOR
\ENDFOR
\STATE \COMMENT{Fine moment cancellation.}
\STATE $s \gets s-1$
\STATE Find $a_1, a_2, a_3$ and $a_4$ satisfying $a_1^2+a_2^2+a_3^2+a_4^2=\mathit{moment}$.
\FOR{$i \in 1,\ldots,4$}
\REPEAT
\STATE $s \gets s+1$
\UNTIL{$h_s=h_{s+1}=0$}\label{gen_c:fine}
\FOR{$j \in 0,\ldots,a_i-1$}
\STATE $c_{n-bkt+skt-j} \gets c_{n-bkt+skt-j}+1$
\STATE $c_{n-bkt+skt+j+1} \gets c_{n-bkt+skt+j+1}-1$
\ENDFOR
\STATE $s \gets s+1$
\ENDFOR
% \RETURN $\vec{c}$
\STATE \textbf{return} $\vec{c}$
\end{algorithmic}
\end{algorithm}

There are two potential pitfalls in Algorithm \ref{A:gen_c}.
First, in step \ref{gen_c:rough}, we need to make sure that the ``while'' loop
terminates successfully. This has already been discussed regarding
Algorithm \ref{A:c_prime}, but we repeat the discussion here briefly. The
total moment when entering the ``while'' loop at
step \ref{gen_c:rough} is bounded by $(k-1)k(k+1)(b+1)t^2/12$. (Here,
multiplication by $b$ stems from the $b$ complete $kt$-sized intervals, and the
extra $+1$ stems from the effect of the remaining elements. Explicitly computing
the moment generated by these elements shows that it can never be
greater than that of a complete interval.) In all but the
last iteration, the counterbalance introduced by adding a new pair of
$(+1,-1)$-choices is known.  The first pair counterbalances by $(b-1)k^2t^2$,
the next by $(b-3)k^2t^2$, and so on. The number of pairs needed, $p$, not
including the last pair, is therefore $p=\lfloor \tilde{p} \rfloor$, where
$\tilde{p}$ is the lowest solution to
$$bk^2t^2\tilde{p}-k^2t^2\tilde{p}^2=(k-1)k(k+1)(b+1)t^2/12,$$
or, equivalently, to
$$k\tilde{p}^2-bk\tilde{p}+(k-1)(k+1)(b+1)/12=0.$$
Using some calculus, and utilizing the information that $n\ge 5tk^2$, as per
the claim of the lemma, and therefore $b\ge 5k$, as well as the knowledge of
which $k$ values are admissible in the present construction, we conclude that
the ratio $\tilde{p}/b$ peaks at $(k,b)=(17,85)$, so
\begin{equation}\label{E:pb_ratio}
\frac{\tilde{p}}{b}\le \frac{1}{2}-\sqrt{\frac{343707}{368475}} \approx 0.017.
\end{equation}
There are,
therefore, many more pairs than are actually needed at this step.
Let $\alpha=1/2-\sqrt{343707/368475}$.

The second potential pitfall for Algorithm \ref{A:gen_c} is that in
step \ref{gen_c:fine} we need to ensure that enough unused intervals
are left for fine-tuning. This corresponds to the equation $b-2p\ge 12$,
because we require
$2$ intervals for the remaining rough-cancellation pair, $8$ for the sum of squares, and a
further $2$ as the maximal amount of space wasted due to the sum of squares
requiring two consecutive ``choice $0$'' intervals each. A stricter condition is
$b-2\tilde{p}\ge 12$. From equation \eqref{E:pb_ratio}, we see that this
condition is met for $b\ge 13$, so certainly also for $b\ge 5k$, because
$k\ge5$.

With this computed $\vec{c}$, we can now proceed with the equivalent of
Algorithm \ref{A:m_special_final}. This remains essentially unchanged, but
has the following modification. In the original
Algorithm \ref{A:m_special_final}, moment cancellation was a two-step process:
first rough-cancellation, then fine-tuning. We now add a third step, before the
original two, meant to simplify handling of the variable $t$.

Recall that the algorithms of Section \ref{S:special} deal with matrices divided
into $k$-length intervals, whereas here we deal with matrices divided into
$kt$-length intervals. It would be most convenient if we could treat the last
$bkt$ columns of matrix $M$ as $[M' \times t]$. In fact, there are only
$8$ of the $b$ intervals of the matrix where $M$ diverges from an
$[M' \times t]$ format, and we can simply avoid using them in
moment cancellation, so they can safely be ignored. (These $8$ intervals are the
$2\times4$ used in the sum of squares.)

In Section \ref{S:special} we already investigated how to correct the moment of
a matrix
like $M'$ and have already established how much moment can be corrected
in such a matrix. The problem is that any such action that has
an effect of magnitude $B$ on $M'$ will have an effect of magnitude $Bt^2$ on
$M$. This method can therefore only handle moments that are multiples of
$t^2$. In $M$, however, the moment is general.

To solve this problem, we add $4$ more intervals to the list of non-stretched
intervals, for a total of $12$. Again, we use Lagrange's four-square theorem
to construct four numbers, $a_1,\ldots, a_4$, each at most $t$, such that the
addition of $\sum_{i=1}^4 a_i^2$ to the moment will make it divide by
$t^2$. Once this is done, the original moment cancellation algorithm is applied
on the $M'$ matrices.

To perform the initial moment cancellation, we pick from each of the $4$ chosen
intervals one element from $\mathit{pvals}$ and one element from
$\mathit{nvals}$, each repeated $t$ times and each known to exist in every
interval, and make the $a_i$ with the highest indices among the $t$ repetitions
of the value taken from $\mathit{pvals}$ into $1$ in $\vec{v}$,
and the $a_i$ with the
lowest indices of the $\mathit{nvals}$ into $-1$. Though this will only create
a counterbalance of magnitude $a_i^2$ when the intervals are consecutive, it
always creates a counterbalance that is congruent to $a_i^2$ in modulo $t^2$.

Finally, the last remaining obstacle is that the algorithm may fail
in one of the two moment cancellation routines that were already introduced in
Section \ref{S:special}. The calculation here is
similar to the
one used in the proof for Lemma \ref{L:base}, but we augment it because the
moment may be larger and because the ability to counterbalance may be
diminished (both due to the added features of $\vec{c}$).

We first revise our estimate regarding how many intervals are needed in order to
ascertain that the fine-tuning step succeeds.
As before,
the case that requires the greatest number of intervals for fine-tuning
is $\mathit{pos}=k-1$, $\mathit{neg}=1$, with the original moment
being $2k-1$. This requires $k-2$ $\mathit{neg}$-pairs (each of which requires
$2$ intervals) and $3$ $\mathit{pos}$-pairs (each of which requires a single
interval), for a total of $2k-1$ intervals.
The difference, however, is that this time there is no partitioning of
$\vec{c}$ into copies of a base $\vec{c'}$. Therefore, the total number of
intervals that are unusable due to
``choice'' changes is bounded by $5$. We describe explicitly the
structure of $\vec{v}$ here.

The lowest indices of $\vec{v}$ correspond to ``$+1$'' choices
and the highest indices are the reverse.
Between these, there may be at most one other ``$-1$'' choice, from
step \ref{gen_c:last} of Algorithm \ref{A:gen_c}. In the lowest-most
``choice $0$'' intervals, $4$ pairs of intervals are used for handling
modulo $k^2t^2$ moment cancellation in $\vec{c}$. These are not used in
moment cancellation on $\vec{v}$.

Other than these $4$ pairs,
any two consecutive ``$+1$'', ``$-1$'' or ``$0$'' choices can be used at this
point for the fine tuning in the choice of $\mathit{neg}$ pairs. The intervals
that are unusable due to ``choice'' changes can be used either for the
$\mathit{pos}$ pairs or for the $4$ intervals used for ensuring that the
moment divides by $t^2$. Because there are no more than $5$ intervals affected
by ``choice'' changes, but $4+3$ (or more) interval roles that do not require
pairing, no interval is truly
unusable due to a ``choice'' change. We therefore reach the conclusion that if
$(2k-1)+2\times4+4=2k+11$
of the $b$ complete $kt$-sized intervals are unused at the end of the rough
moment-cancellation stage, these are enough to complete fine tuning properly.

We now turn to the question of how much needs to be counterbalanced at the
rough-cancellation stage. The calculation repeats the one that was presented in
the proof of Lemma \ref{L:base}, with the necessary changes and adding in the
effects of the new elements. We summarize here briefly by enumerating the
elements to be accounted for and their effect.
\begin{enumerate}
\item The $-(k-1)/2,\ldots, (k-1)/2$ progression in ``choice $0$'' intervals
accounts for $(k^2-1)t^2/4$ per interval. The $-(k-3)/2,\ldots, (k-3)/2$
progression in ``choice $1$'' and ``choice $-1$'' intervals accounts for less.
Together with the remaining types of complete intervals, these amount
to no more than $b(k^2-1)t^2/4$.
\item ``choice $1$'' and ``choice $-1$'' have pairs of $(-(k-1)/2,(k-1)/2)$ and
$(-(k+1)/2,(k+1)/2)$ shared among them. Originally, $(f,s)$ pairs were chosen
in $\vec{c}$ so as to counterbalance at most $(k-1)k(k+1)(b+1)t^2/12$. Each
such pair counterbalanced $(f-s)k^2t^2$. In the present context, each such
pair causes at most $2(f-s+1)kt^2$ moment, so the total of all pairs is
bounded by $(k-1)(k+1)(b+1)t^2/6+2pkt^2$, where $p$ is the number of pairs,
known to satisfy $p\le \alpha b$.
\item The $4$ pairs of interval used to form a sum of squares in creating
$\vec{c}$ differ from regular intervals by the removal of at most $t$ elements
and their replacement by at most $t$ others. This change is complemented by a
change in the neighboring interval. Hence, this contributes at most
$4kt^2$ to the moment, per pair, or $16kt^2$ in total. (The fact that the
elements that have not been replaced
may have shifted positions does not enter the calculation, because we have
already taken into account the maximal moment attainable by any interval, as
long as its elements are balanced.)
\item The first $n-bkt$ indices can be considered in two parts: first, we have
$n \bmod t$ indices that contribute no more than $t^2/2$ to the moment. The
rest of the at most $(k-1)t$ indices are balanced, and cannot contribute more
moment than $(k-1)^2t^2/4$. In total, this is bounded by $k^2t^2/4$.
\item The cancellation actions of previous $i$ iterations contribute twice their
original moment. As a result, all of the above has to be multiplied
by $3^{i-1}$.
\item In adding the sum of squares that cancels the moment of $\vec{v}$
modulo $t^2$, each added pair can cause an inadvertent moment of at most
$kt^2$, for a total of $4kt^2$. (This does not accrue a $3^{i-1}$ factor,
because it is part of the $\vec{v}$ moment cancellation process, not part of
the initial moment of $\vec{c}$.)
\end{enumerate}

In total, this sums up to
$$3^{i-1}t^2\left(b\left(\frac{5}{12}k^2+2\alpha k - \frac{5}{12}\right)
+\frac{5}{12}k^2+16k-\frac{1}{6}\right)+4kt^2,$$
and to guarantee the success of the algorithm, this should be less than
the moment that can be produced in the rough-moment-cancellation step,
minus $2k+11$ unused intervals.
The moment that can be generated in this way is bounded from
below by
$$\frac{1}{2}(3^{i-1}+1)\left\lfloor\frac{1}{2}(b-(2k+11))\right\rfloor
\left(\left\lceil\frac{1}{2}(b+(2k+11))\right\rceil-1\right)kt^2.$$

Substituting in $b\ge5k$, we get that this is true if $k\ge16$, which is true
if $m\ge3$.
\end{proof}

We remark that $b\ge5k$ is not a tight bound. For a large enough $m$, the methods used here continue to
work for any $b\ge\beta k$ when $\beta>\tfrac{5+\sqrt{61}}{3}\approx 4.27$.

\section{Bounding $B(n)$ and $B'(n)$}\label{S:bound}

We now turn to proving Theorem \ref{T:B_prime}, of which our main theorem,
Theorem \ref{T:B}, is a direct corollary due to $B'(n)\ge B(n)$.

\begin{proof}[Proof of Theorem \ref{T:B_prime}]
We construct, explicitly, a homogeneous $m\times n$ \M matrix for any $n$, with
an $m$ value that is $\log_3 n+\O(\log \log n)$.

Specifically, we construct a homogeneous $\tilde{m}\times n$ matrix that is
$\O(1)$-part
piecewise-monotone, with a $\tilde{m}$ value that is $\log_3 n+\O(\log \log n)$,
then use
Lemma \ref{L:completion} to make it into a \M matrix by adding $\O(1)$
weighings.

The homogeneous $\O(1)$-part piecewise-monotone weigh-set is, in turn, the
union of $s$ homogeneous
weigh-sets, $\{M_i\}_{i=1}^{s}$, with $M_i \in \mathcal{M}(m_i,k_i,t_i,n)$, for
all $i$, where the parameters $m_i$, $k_i$, $t_i$ and $s$ are determined as
follows.
\begin{enumerate}
\item $\forall i, t_i=\prod_{j=1}^{i-1} k_j$.
\item $\forall i, m_i=\left\lfloor \log_3\left(\tfrac{3}{2}\sqrt{n / 5t_i }\right) \right\rfloor$.
\item $\forall i$, $k_i$ is chosen to be the largest prime smaller than
$2 \times 3^{m_i-1}$.
\item The parameter $s$ is chosen to be maximal, subject to
$\forall i, m_i\ge 4$.
\end{enumerate}

The description above defines all parameters uniquely, as is demonstrated by
Algorithm \ref{A:parameter_choosing}.

\begin{algorithm}[!h]
\caption{Choosing the parameters $m_i$, $k_i$, $t_i$ and $s$}
\label{A:parameter_choosing}
\begin{algorithmic}[1]
\STATE $s \gets 0$
\STATE $t_1 \gets 1$
\STATE $m_1 \gets \left\lfloor \log_3\left(\tfrac{3}{2}\sqrt{n / 5}\right) \right\rfloor$
\WHILE{$m_{s+1}\ge4$}
\STATE $s \gets s+1$
\STATE $k_s \gets \max\{k\colon \text{$k$ prime and $k<2 \times 3^{m_s-1}$}\}$
\STATE $t_{s+1} \gets t_s k_s$
\STATE $m_{s+1} \gets \left\lfloor \log_3\left(\tfrac{3}{2}\sqrt{n / 5t_{s+1}}\right) \right\rfloor$
\ENDWHILE
\end{algorithmic}
\end{algorithm}

Furthermore, by Lemma \ref{L:gen_base}, there exist weigh-sets $M_i$ that
match these specifications.

By the same reasoning as in Lemma \ref{L:piecewise_strategy}, the weigh-set
constructed in this fashion is $\lceil n/t_s \rceil$-part piecewise-monotone,
which, due to the criterion for choosing $s$, is $\O(1)$-part piecewise-monotone,
as necessary. We have shown, therefore, the construction of a \M matrix with
dimensions $m \times n$, for an arbitrary $n$, where $m$ is
$\O(1)+\sum_{i=1}^{s} m_i$. We now turn to proving that
$m-\log_3 n$ is $\O(\log \log n)$.

As we have seen, the halting criterion ensures that $n/t_s$ is $\O(1)$ and, as a
result, $k_s$ is also $\O(1)$ and
$n/\prod_{i=1}^s k_i$ is $\O(1)$.
The value $\log_3 n$ is therefore $\O(1)+\sum_{i=1}^s \log_3 k_i$.
The value $m-\log_3 n$ can therefore be written as
$\O(1)+\sum_{i=1}^s (m_i-\log_3 k_i)$.

A simple upper bound on $m_i-\log_3 k_i$ follows from Bertrand's postulate,
which we have already used amply in the construction, according to which
$k_i>3^{m_i-1}$, and therefore $m_i-\log_3 k_i<1$. This ensures that
$m-\log_3 n$ is $\O(s)$. We therefore turn to bounding $s$ from above.

Consider the list of $k_i$ values. By construction, $k_i$ is greater than $1/3$
the largest power of $3$ that is smaller than $\tfrac{3}{2}\sqrt{n / 5t_i}$.
Specifically, it is greater than $\sqrt{n / 5t_i}/6$. On the other hand,
$k_{i+1}$ is smaller than $2/3$ the largest power of $3$ that is smaller
than $\tfrac{3}{2}\sqrt{n / 5t_{i+1}}$. It is therefore smaller than
$\sqrt{n / 5t_{i+1}}=\sqrt{n / 5t_i k_i}$, leading to the equation
\begin{equation}\label{E:k_progression}
k_{i+1}<\frac{6 k_i}{\sqrt{k_i}} = 6 \sqrt{k_i}.
\end{equation}

Consider the sequence $\tilde{k}_i$, defined as follows, for a general value of
$n$ and for $k_i$ and $s$ values calculated from it:
$\tilde{k}_i\defeq\min_n \{k_{s+1-i}/36\}$. The sequence $\tilde{k}_i$, up to
an order reversal and division by $36$, gives a lower bound for the $k_i$ for
any $n$. In particular, because $m_s\ge 4$, we have
$\tilde{k}_1\ge\tfrac{53}{36}>1$, and due to Equation \eqref{E:k_progression}
we have $\tilde{k}_{i+1}>\tilde{k}_i^2$. In particular, for all $i$,
$\tilde{k}_i\ge \gamma^{2^i}$, for $\gamma=\sqrt{53/36}$.

Clearly, $k_1\le n$, so $\tilde{k}_s\le n/36$, leading to the equation
$n/36 \ge \gamma^{2^s}$, so $s$ is $\O(\log \log n)$.
\end{proof}

We remark that throughout we have only used Bertrand's postulate, certifying
the existence of a prime between $a$ and $2a$. However, the largest prime
smaller than $2a$, for a large enough $2a$, is known to be quite close to $2a$.
Specifically, a result by Dusart \cite{Dusart:Prime} is that for a large enough
$x$ a prime always exists between $x$ and
$\left(1+(2 \ln^2 x)^{-1}\right)x$.
Integrating this tighter bound into our calculation of
$m_i-\log_3 k_i$ it is possible to show that
$m$ is $\log_3 n + \delta \log_2 \log_B n + \O(1)$, where 
$\delta=\log_3 \tfrac{3}{2}$ and the
choice of $B$ is arbitrary, and only affects the $\O(1)$.

Though, mathematically speaking, $\delta \log_2 \log_B n$ is
clearly an
unbounded function of $n$, it is interesting to note that even when choosing
$B=2$, the value of this function only reaches $3$ when $n>10^{80}$, which
is more than the estimated number of atoms in the
universe \cite{Gribbin:universe}. It goes up to $4$ at $n>10^{551}$ and up to
$5$ at $n>10^{3604}$.
These numbers demonstrate that $B(n)$ is, indeed, very close to $\log_3 n$, as
was conjectured in \cite{Khovanova:Baron}.

\subsection*{Acknowledgements}
The author wishes to thank Ian Wanless for introducing him to the problem.

% \bibliographystyle{plain}

\begin{thebibliography}{10}

\bibitem{Tokarev:Olympiad}
Problems from the last round of {L}{I}{V} {M}oscow {M}athematical {O}lympiad.
\newblock {\em Kvant}, 9:70--71, 1991.

\bibitem{Brand:Tightening}
M.~Brand.
\newblock Tightening the bounds on the {B}aron's omni-sequence.
\newblock {\em Discrete Mathematics}, 312(7):1326--1335, 2012.

\bibitem{Cormen:algorithms}
T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C.~Stein.
\newblock {\em Introduction to Algorithms}, Section 8.1: Lower bounds
  for sorting, pages 165--168.
\newblock MIT Press and McGrow-Hill, 2nd edition, 2001.

\bibitem{Dusart:Prime}
Pierre Dusart.
\newblock In\'egalit\'es explicites pour {$\psi(X)$}, {$\theta(X)$}, {$\pi(X)$}
  et les nombres premiers.
\newblock {\em C. R. Math. Acad. Sci. Soc. R. Can.}, 21(2):53--59, 1999.

\bibitem{Dyson:Pennies}
F.~J. Dyson.
\newblock 1931. the problem of the pennies.
\newblock {\em The Mathematical Gazette}, 30(291):231--234, 1946.

\bibitem{Gribbin:universe}
J.~Gribbin.
\newblock {\em In Search of the Big Bang: Quantum Physics and Cosmology}.
\newblock Heinemann, 1986.

\bibitem{Halbeisen:general_counterfeit}
L.~Halbeisen and N.~Hungerb\"{u}hler.
\newblock The general counterfeit coin problem.
\newblock {\em Discrete Mathematics}, 147(1--3):139--150, 1995.

\bibitem{Hardy:Inequalities}
G.~H. Hardy, J.~E. Littlewood, and G.~P{\'o}lya.
\newblock {\em Inequalities}.
\newblock Cambridge, at the University Press, 1952.
\newblock 2d ed.

\bibitem{Ireland:number_theory}
Kenneth Ireland and Michael Rosen.
\newblock {\em A Classical Introduction to Modern Number Theory}, volume~84 of
  {\em Graduate Texts in Mathematics}.
\newblock Springer-Verlag, New York, second edition, 1990.

\bibitem{A186313:Omnisequence}
T.~Khovanova and J.B. Lewis.
\newblock A186313.
\newblock \url{oeis.org/A186313}.
\newblock [Online; accessed 10 March 2012].

\bibitem{Khovanova:Baron}
T.~Khovanova and J.B. Lewis.
\newblock {B}aron {M}\"{u}nchhausen redeems himself: Bounds for a coin-weighing
  puzzle.
\newblock {\em The Electronic Journal of Combinatorics}, 18(1):37, 2011.

\bibitem{Khovanova:Sequence}
Tanya Khovanova, Konstantin Knop, and Alexey Radul.
\newblock Baron {M}\"unchhausen's sequence.
\newblock {\em J. Integer Seq.}, 13(8):Article 10.8.7, 18, 2010.

\bibitem{Knuth:programming}
D.E. Knuth.
\newblock {\em The Art of Computer Programming, Volume 3: Sorting and
  Searching}, Section 5.3.1: Minimum-Comparison Sorting, pages
  180--197.
\newblock Addison-Wesley, 2nd edition, 1997.

\bibitem{Mood:Hotelling}
Alexander~M. Mood.
\newblock On {H}otelling's weighing problem.
\newblock {\em Ann. Math. Statistics}, 17:432--446, 1946.

\bibitem{Smith:counterfeit}
C.A.B. Smith.
\newblock The counterfeit coin problem.
\newblock {\em Mathematical Gazette}, 31:31--39, 1947.

\bibitem{Steinhaus:snapshots}
H.~Steinhaus.
\newblock {\em Mathematical Snapshots}.
\newblock Dover Publications, 3rd edition, 1999.

\end{thebibliography}
\end{document} 
