\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P1}{19(4)}{2012}

\usepackage{caption2}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\usepackage{amsmath, amsthm}
\usepackage{amssymb}
\usepackage{cite}
\usepackage{pst-all}
\usepackage{verbatim}

%\ifx\pdftexversion\undefined
  \usepackage[dvips]{graphics}
%\else
  %\usepackage[pdftex]{graphics}
%\fi


\input{figs.tex}

\makeatletter
\def\adots{\mathinner{\mkern1mu\raise\p@\hbox{.}\mkern2mu
    \raise4\p@\hbox{.}\mkern2mu\raise7\p@\vbox{\kern7\p@\hbox{.}}\mkern1mu}}
\makeatother

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}{Corollary}
\newtheorem{corollaries}{Corollaries}
\newtheorem{proposition}{Proposition}
\newtheorem{lemma}{Lemma}
\newtheorem{conjecture}{Conjecture}
\newtheorem{definition}{Definition}
\newtheorem{problem}{Problem}

\newcommand{\dotdot}{{\,..\,}}
\newcommand{\fig}{Fig$.$ }
\newcommand{\figs}{Figs$.$ }
\newcommand{\display}{\begin{displaymath}}
\newcommand{\offplay}{\end{displaymath}}
\newcommand{\eqn}{\begin{eqnarray}}
\newcommand{\eqns}{\begin{eqnarray*}}
\newcommand{\uneq}{\end{eqnarray}}
\newcommand{\uneqs}{\end{eqnarray*}}
\newcommand{\mioperatorname}[1]{\mathop{\mathrm{#1}}}
\newcommand{\lcm}{\mioperatorname{ lcm}}
\newcommand{\spam}{\mioperatorname{ span}}
\newcommand{\ov}{\overline}
\newcommand{\un}{\underline}
%\newcommand{\mod}{\textrm{ mod }}
\newcommand{\zplus}{\mathbb{Z}_+}
\newcommand{\zz}{\mathbb{Z}}
\newcommand{\rr}{\mathbb{R}}
\newcommand{\nn}{\mathbb{N}}
\newcommand{\cc}{\mathbb{C}}
\newcommand{\qq}{\mathbb{Q}}
\newcommand{\ff}{\mathbb{F}}
\newcommand{\mcal}{\mathcal}
\newcommand{\mc}{\mathcal}
\newcommand{\scr}{\mathscr}
\newcommand{\littlemod}{\scriptsize{\textrm{ mod }}}
\newcommand{\back}{\backslash}
\newcommand{\supp}{\mioperatorname{ supp}}
\newcommand{\diam}{\mioperatorname{ diam}}
\newcommand{\vol}{\mioperatorname{ vol}}
\newcommand{\for}{\textrm{ for }}
\newcommand{\rmand}{\textrm{ and }}
\newcommand{\F}{\mcal{F}}
\newcommand{\D}{\mcal{D}}
\newcommand{\A}{\mcal{A}}
\newcommand{\mS}{\mcal{S}}
\newcommand{\B}{\mcal{B}}
\newcommand{\G}{\mcal{G}}
\newcommand{\I}{\mcal{I}}
\newcommand{\J}{\mcal{J}}
\newcommand{\mL}{\mcal{L}}
\newcommand{\mH}{\mcal{H}}
\newcommand{\Abar}{\overline{\mcal{A}}}
\newcommand{\Bbar}{\overline{\mcal{B}}}
\newcommand{\Lbar}{\overline{\mcal{L}}}
\newcommand{\one}{{\mathbf{1}}}
\newcommand{\ra}{\rightarrow}
\newcommand{\evar}{\varepsilon}
\newcommand{\ee}{{\evar_0}}
\newcommand{\ignore}[1]{}

\title{The lowest-degree polynomial with nonnegative coefficients divisible by the $n$-th cyclotomic polynomial}

\author{John P. Steinberger\thanks{Supported by the National Basic Research Program of China Grant
2011CBA00300, 2011CBA00301, the National Natural Science Foundation of
China Grant 61033001, 61061130540, 61073174, and by NSF grant 0994380.}\\
\small Institute for Theoretical Computer Science\\[-0.8ex]
\small Tsinghua University\\[-0.8ex] 
\small\tt jpsteinb@gmail.com
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Oct 7, 2011}{Sep 23, 2012}{Oct 18, 2012}\\
\small Mathematics Subject Classifications: 11R09, 90C57, 90C05, 05E99}

\ignore{
\linespread{1.1}
\author{John P. Steinberger\thanks{Supported by the National Basic Research Program of China Grant
2011CBA00300, 2011CBA00301, the National Natural Science Foundation of
China Grant 61033001, 61061130540, 61073174, and by NSF grant
0994380.}
\\Institute for Theoretical Computer Science\\Tsinghua University}

%\title{On the least degree vanishing sum of $n$-th roots of unity}
}


\begin{document}
\maketitle

\begin{abstract}
We pose the question of determining the lowest-degree polynomial with nonnegative coefficients divisible by the $n$-th cyclotomic polynomial $\Phi_n(x)$.
We show this polynomial is $1 + x^{n/p} + \cdots + x^{(p-1)n/p}$ where $p$ is the smallest prime dividing $n$ 
whenever $2/p > 1/q_1 + \cdots + 1/q_k$, where $q_1, \ldots, q_k$ are the other (distinct) primes besides $p$ dividing $n$.
Determining the lowest-degree polynomial with nonnegative coefficients divisible by $\Phi_n(x)$ remains open in the general case, 
though we conjecture the existence of values of $n$ for which this degree is, in fact, less than $(p-1)n/p$.
\end{abstract}

\section{Introduction}

The $n$-th cyclotomic polynomial $\Phi_n(x)$ is $\Pi(x-\zeta)$ where the product is taken over the distinct primitive $n$-th roots of unity $\zeta$.
%The $n$-th cyclotomic polynomial $\Phi_n(x)$ is the unique monic polynomial whose roots are exactly the primitive $n$-th roots of unity with multiplicity 1 each. 
It is well-known that $\Phi_n(x)$ has integer coefficients and that $\Phi_n(x)$ is irreducible over $\qq$. 
%Moreover if $n = p^\alpha$ is a prime power then
%Some cyclotomic polynomials have a simple form. For example if $n = p^\alpha$ is a prime power then
%\eqn
%\label{struct1} \Phi_n(x) = 1 + x^{p^{\alpha - 1}} + x^{2p^{\alpha - 1}} + \cdots + x^{(p-1)p^{\alpha - 1}}.
%\uneq
%However when $n$ has three or more prime divisors 
%In the general case, however, there is little structure to the coefficient sequence of $\Phi_n(x)$.
%and if $n = p^\alpha q^\beta$ is a product of two prime powers then the coefficients of $\Phi_n(x)$ are all 0 or $\pm 1$, and are determined by a simple criterion \cite{lamleungbaby}. When $n$ has 3 or more prime factors, however, $\Phi_n(x)$ looks mostly chaotic (apart from the fact that it is palindromic) and as a consequence its coefficients remain well-studied \cite{bachman1, bachman2, bateman, vaughan1, vaughan2}.

In this paper we consider the problem of determining the polynomial of lowest degree with nonnegative coefficients divisible by $\Phi_n(x)$. The problem doesn't make sense for $n = 1$ since $\Phi_1(x) = x - 1$ and $x = 1$ %has 1 as a root, which 
cannot be the root of any polynomial with nonnegative coefficients (by ``polynomial'' we always mean ``nonzero polynomial''). But when $n > 1$ then $\zeta_n = e^{2\pi i/n}$ is a root of
$$
1 + x + x^2 + \cdots + x^{n-1}
$$
so $\Phi_n(x)$ divides a polynomial with nonnegative coefficients. 
%the above polynomial and in particular divides some polynomial with nonnegative coefficients. 
The question is to determine the lowest degree such polynomial. %We say ``the'' but
%Note it isn't clear there is a unique such polynomial up to scalar multiplication of the coefficients, since 
 It does not matter whether we consider only polynomials in $\rr[x]$, $\qq[x]$ or even $\zz[x]$ since the problem can be reduced to the 
feasibility of a rational system of linear inequalities, 
and since rational systems have solutions over $\qq$ 
if and only if they have solutions over $\rr$ (and there is obviously no difference between $\qq$ and $\zz$). In fact every solution in $\rr[x]$ is a convex combination of solutions in $\qq[x]$, by the same considerations. A priori, the solution may not be unique up to scalar multiplication.

Working over $\zz[x]$ suggests a physical analogy. Assume $n$ equally spaced holes are drilled around the circumference of a circular plate 
and that stackable pegs are made to fit the holes. 
Then putting a stack of $a_i$ pegs in the $i$-th hole, $i = 0 \dots n-1$, yields a plate that is perfectly balanced around the center if and only if
\eqn
\label{vanishing} a_0 + a_1\zeta_n + \cdots + a_{n-1}\zeta_n^{n-1} \,= \,0
\uneq
which happens if and only if $\Phi_n(x)|a_0 + a_1x + \cdots + a_{n-1}x^{n-1}$. Therefore balanced configurations of pegs are in one-to-one correspondence with polynomials with nonnegative integer coefficients divisible by $\Phi_n(x)$. The degree of a polynomial associated with a balanced configuration of pegs is equal to the largest index of a nonempty hole.
Since the balance of the plate is not affected by rotation it is clearly advantageous to rotate the plate until the longest sequence of consecutive empty holes occurs between hole 0 (that contains a peg) and the peg with largest index. 
Thus finding the lowest degree polynomial with nonnegative coefficients divisible by $\Phi_n(x)$ is equivalent to finding a (nonempty) balanced configuration of pegs with the longest possible consecutive sequence of empty holes, for a plate with $n$ equally spaced holes.

(We note that for the above analogy to apply integral numbers of pegs must be used; otherwise if we are allowed to saw off our pegs such as to place some arbitrary height of pegs in a given hole we can always balance the plate with just 3 nonempty holes, say hole 0, $\lfloor n/2 \rfloor$ and $\lceil n/2 \rceil$. The polynomial corresponding to this configuration will indeed have $\zeta_n$ as a root but will not be divisible by $\Phi_n(x)$, due to the fact that $\Phi_n(x)$ is irreducible over $\qq[x]$ but not over $\rr[x]$.)

Balanced configurations can be quite intricate \cite{meisminimal} but some are simple. In particular for every prime $p$ dividing $n$ one can make a regular $p$-gon, which is balanced. To maximize the gaps between consecutive pegs one should take $p$ to be the smallest prime dividing $n$. In this case gaps have $n/p - 1$ holes, and the associated polynomial (after rotation to place a peg in hole 0) is $1 + x^{n/p} + \cdots + x^{(p-1)n/p}$. 
This polynomial seems like a ``natural enough'' candidate for the lowest degree
polynomial with nonnegative coefficients divisible by $\Phi_n(x)$, which leads to the following conjecture.

%In fact we conjecture this is the best solution.

\begin{conjecture}\label{conj}
The lowest degree monic polynomial with nonnegative coefficients divisible by $\Phi_n(x)$, $n > 1$, is $1 + x^{n/p} + \cdots + x^{(p-1)n/p}$ where $p$ is the smallest prime dividing $n$.
\end{conjecture}

\noindent 
In particular, Conjecture \ref{conj} would imply that the solution is unique of up to scalar multiplication. 

In fact, we do \emph{not} believe Conjecture \ref{conj} is true, even if we have not disproved it.
Our skepticism stems from the fact that Conjecture \ref{conj} implies the feasibility of a certain
system of rational linear inequalities that, when $n$ is a product of large number of distinct
large primes, seems very unlikely to be feasible. Nonetheless, due to the size of the systems
involved, finding a counterexample is quite challenging from a computational standpoint, and our
only ``hard'' results are positive results in favor the conjecture.

Since the polynomial  $1 + x^{n/p} + \cdots + x^{(p-1)n/p}$ has smaller degree when $p$ is small, 
it seems, intuitively, that it should be easier to prove Conjecture \ref{conj} when $p$ is small. 
This is reflected in our main result.

\begin{theorem}\label{main}
Conjecture \ref{conj} holds when $n$ is even or when $n$ is a prime power or when $2/p > 1/q_1 + \cdots + 1/q_k$ where $q_1, \ldots, q_k$ are the other primes besides $p$ dividing $n$.
\end{theorem}

\noindent The smallest value of $n$ not covered by Theorem \ref{main} is $n = 11\cdot 13 \cdot 17 \cdot 19 = 46189$ 
and the next few values are $n = 96577, 215441, 392863, 508079, \ldots$. 
Checking Conjecture \ref{conj} for these (specific) values of $n$ is, in theory, 
a finite problem each time (expressible
as a linear program), but we found the computational scale of these
problems too large to handle conveniently (our measure of convenience
being a few days computation on a laptop).
% for $n =  46189$.

The case of Theorem \ref{main} when $n = p^\alpha$ is a prime power follows from the fact that
\eqn
\nonumber \label{struct1} \Phi_{p^\alpha}(x) & = & 1 + x^{p^{\alpha - 1}} + x^{2p^{\alpha - 1}} + \cdots + x^{(p-1)p^{\alpha - 1}}\\
\nonumber                                   & = & 1 + x^{n/p} + \cdots + x^{(p-1)n/p}
\uneq
%\eqref{struct1} 
and $\Phi_n(x)$ cannot divide a polynomial of lower degree than itself
or divide a non-scalar-multiple of same degree (when $n$ is divisible
by two or more primes $\Phi_n(x)$ no longer contains only nonnegative
terms). The case when $n$ is even follows from elementary geometrical
considerations: if $p = 2$ then $(p-1)n/p$ is half way around the
plate, and one cannot balance the plate using pegs strictly contained
in half of the plate; moreover if a balanced configuration uses holes
$0 \dots n/2$ it must not place any pegs in holes $1 \dots n/2 - 1$,
and it must place the same number of pegs in holes 0 and $n/2$, hence uniqueness.

% explained below. 
Theorem \ref{main} implies Conjecture \ref{conj} for all cases when $n$ has three or fewer primes in its factorization since $2/p > 1/q_1$ and $2/p > 1/q_1 + 1/q_2$ by virtue of the fact that $p$ is the smallest prime dividing $n$. The case when $n$ is divisible by exactly two primes $p$, $q$ already follows from a result of deBruijn \cite{bruijn3}, who showed that any polynomial with nonnegative coefficients divisible $\Phi_n(x)$ can then be written as $f(x)(1 + x^{n/p} + \cdots + x^{(p-1)n/p}) + g(x)(1 + x^{n/q} + \cdots + x^{(q-1)n/q})$ for some polynomials $f(x)$, $g(x)$ with nonnegative coefficients.

Because $\Phi_{np}(x) = \Phi_n(x^p)$ when $p$ is a prime dividing $n$, determining the lowest degree polynomial with nonnegative coefficients divisible by $\Phi_n(x)$ is equivalent to determining the lowest degree polynomial with nonnegative coefficients divisible by $\Phi_{n'}(x)$ where $n'$ is the squarefree part of $n$ (indeed the above identity implies that if $f(x)$ is any polynomial divisible by $\Phi_{n'}(x)$ then $f(x^{n/n'})$ is divisible by $\Phi_n(x)$, and that any polynomial divisible by $\Phi_n(x)$ remains divisible by $\Phi_n(x)$ after removing all terms whose exponents are not $0$ mod $n/n'$ (or not $z$ mod $n/n'$ for any $z$)). This is why neither Conjecture \ref{conj} nor Theorem \ref{main} take into account the multiplicity with which primes divide $n$.

We note that Conjecture \ref{conj} would have the following type of non-intuitive consequence: if $n$, say, is the product of all primes between $10^6$ and $10^{100}$, then a nonempty balanced configuration of pegs could still not leave empty any section of size $1/10^6$-th the length of the total circumference of the plate. One can extend this idea to plates with infinitely many holes: fix a prime $p$, and assume that we can place pegs at any position along the circumference of the plate whose polar angle is rational multiple of $2\pi$ where the denominator of the rational coefficient is not divisible by any prime smaller than $p$ (this amounts to considering vanishing sums using roots of unity whose orders are not divisible by any prime smaller than $p$); then if Conjecture \ref{conj} is true, no nonempty balanced configuration can leave empty a section of length $1/p$ of the total circumference. This follows because any balanced configuration is finite, and one can take $n$ to be the lcm of the orders of the roots of unity used.

While the question of ``debunking'' Conjecture \ref{conj} is of great interest, the
remainder of the paper mostly focuses on our actual result, Theorem \ref{main} and its
proof (we do briefly re-explain our pessimism at
the end of Section \ref{sec:lowdim}). The methods used for the proof of Theorem \ref{main} are quite geometric and of
potential independent interest. 
%However, the reason for our pessimism
%vis-\'a-vis Conjecture \ref{conj} is discussed in more detail at the
%end of Section \ref{sec:lowdim}.

\section {Methods}\label{sec:methods}

For the rest of the paper $n$ denotes a squarefree integer $> 1$. 
It will be convenient to write the prime factorization of $n$ as 
$pq_1\cdots q_k$ where $p$ is the smallest prime dividing $n$ and 
$q_1$, $\ldots$, $q_k$ are the remaining primes dividing $n$. We may 
assume $k \geq 1$ since Conjecture \ref{conj} is true for $n = p$. 
We put $P = n/p$, $Q_1 = n/q_1, \ldots, Q_k = n/q_k$.

Let $V_n \subseteq \rr^n$ be the vector space consisting of 
all $n$-tuples $(a_0, \dots, a_{n-1})$ 
such that $\Phi_n(x) | a_0 + a_1x + \cdots + a_{n-1}x^{n-1}$. 
We index vectors starting at 0 rather than at 1 (i.e.,~write
$(x_0, \ldots, x_{n-1})$ rather than $(x_1, \ldots, x_n)$).
For convenience we partition the set of indices $\{0, 1, \ldots, n-1\}$
into the following sets %$\mH$, 
$\F_0, \ldots, \F_{p-1}$:
\eqns
\mH & = & \{0, P, 2P, \ldots, n - P\}\\
\F_0 & = & \{1,2,\dots,P-1\}\\
\F_1 & = & \{P+1,P+2,\dots,2P-1\}\\
  & \vdots & \\
\F_{p-1} & = & \{(p-1)P+1,(p-1)P+2,\dots, n-1\}.
\uneqs
We also let $\F^+ = \F_0 \cup \cdots \cup \F_{p-2}$ and $\F^- = \F_{p-1}$.
For a set of indices $\A \subseteq \{0, 1, \ldots, n-1\}$ and 
a vector $v = (v_0, \ldots, v_{n-1}) \in \rr^n$, we say $v$
\emph{is 0 on $\A$} (resp$.$ is positive on $\A$, etc) if $v_i = 0$
for $i \in \A$ (resp$.$ $v_i > 0$ for $i \in \A$, etc).

Let $1_\mH \in \rr^n$ be the incidence vector of $\mH$; this is also the coefficient vector the polynomial
$$
1 + x^{n/p} + \cdots + x^{(p-1)n/p} = 1 + x^P + \cdots + x^{(p-1)P}.
$$
Thus $1_\mH \in V_n$. Conjecture \ref{conj} is equivalent to the statement that 
the only nonnegative vectors in $V_n$ that are 0 on $\F^- = \F_{p-1}$
are scalar multiples of $1_\mH$.

\ignore{
Let $v^* \in V_n$ be the coefficient vector of the polynomial
$$
1 + x^{n/p} + \cdots + x^{(p-1)n/p} = 1 + x^P + \cdots + x^{(p-1)P}.
$$
%That is, the index $i$ entry of $v_*$ is 1 if $i \in \{0,P,\ldots,n-P\}$, and 0 otherwise.
%Thus, if $v^*_i$ denotes the index $i$ entry of $v^*$, then $v^*_i = 1$ if $i \in \mH$ and $v^*_i = 0$ if $i \notin \mH$.
Thus, $v^*$ is the vector that is 1 in $\mH$ and 0 outside $\mH$.
%$i \equiv 0 \mod P$ and is 0 otherwise, $i \in \{0, \ldots, n-1\}$.
Conjecture \ref{conj} %is true (for a given value of $n$) if and only if
is equivalent to the statement that 
the only nonnegative vectors in $V_n$ that are 0 on $\F^- = \F_{p-1}$
%whose last $P - 1$ entries are 0 (i.e.~that are 0 on $\F^- = \F_{p-1}$) 
are scalar multiples of $v_*$.
}

Let $\langle u, v \rangle$ denote the usual dot product of vectors
in $\rr^n$ and let $V_n^\perp = \{u \in \rr^n: \langle u, v \rangle = 0$ for all $v \in V_n\}$ 
be the orthogonal complement of $V_n$ in $\rr^n$.
Our results are based on the following lemma. 
%(stated for a squarefree $n$ with at least two prime factors).

\begin{lemma}\label{basiclem}
%Conjecture \ref{conj} holds for a given value of $n$ (squarefree) 
%Let $n$ be squarefree. Then 
Conjecture \ref{conj} holds for (a squarefree) $n$ if and only if there exists a vector
$w \in V_n^\perp$ such that $w$ is positive on $\F^+$ and zero on $\mH$.
%, $w = (w_0, \ldots, w_{n-1})$, such that $w_i > 0$ for $i \in \F^+$ and $w_i = 0$ for $i \in \mH$.
%$i \in \{0,1,\ldots,n-P\}\back \{0,P,\ldots,n-P\}$ and such that $w_i = 0$ for $i \in \{0,P,\ldots,n-P\}$.
\end{lemma}

\noindent
The proof of Lemma \ref{basiclem} requires the following elementary proposition,
which is a consequence of the Farkas lemma for systems of linear inequalities. 
We recall that the Farkas lemma (in one
of its many incarnations) states that a linear system 
$Ax = b$, $x \geq 0$ has no solution if and only if there
exists a $y$ such that $y^TA \geq 0$ and $y^Tb < 0$. (For background,
see e.g$.$ \cite{schrijver}; by writing $x \geq 0$ we mean that each
coordinate of $x$ is nonnegative.)

\begin{proposition}\label{farkie}
Let $A \in \rr^{m \times n}$ be a real matrix and let $\J \subseteq \{0, \ldots, n-1\}$.
Then there is no $x = (x_0, \ldots, x_{n-1}) \in \rr^n$ such that $x \geq 0$, $Ax = 0$ and such that
$x_j > 0$ for at least one $j \in \J$ if and only if there exists a vector $y \in \rr^m$ such that $y^TA \geq 0$
and such that $(y^TA)_j > 0$ for all $j \in \J$.
\end{proposition}

\begin{proof}
If $y$ exists then $x$ cannot exist, since otherwise $0 > (y^TA)x = y^T(Ax) = 0$. 

For the other direction, assume $x$ does not exist. Then for each $j \in \J$ the
system $Ax = 0$, $x_j = 1$, $x \geq 0$ has no solution; by the Farkas lemma,
this implies that for each $j \in \J$ there is a vector $(y^j,z^j) \in \rr^m \times \rr = \rr^{m+1}$ 
such that $(y^j)^TA + z^je_j \geq 0$ (where $e_j$ is the $j$-th unit vector) 
and such that $z^j < 0$. In particular, $(y^j)^TA \geq 0$ and
$((y^j)^TA)_j > 0$, so adding the vectors $y^j$, $j \in \J$ 
gives the desired $y$.
\end{proof}

\begin{proof}[Proof of Lemma \ref{basiclem}.]
Assume first that $w$ exists. Let $v \in V_n$ be a nonnegative vector
that is 0 on $\F^-$. 
Then $\langle v, w \rangle = 0$ implies that $v$ is 0 on $\F^+$.
So $v$'s support is contained in $\mH$, and $v$ must be a scalar
multiple $1_\mH$ by the irreducibility\footnote{More precisely,
if the polynomial associated to $v$ is $a_0 + a_1x^P + \cdots + a_{n-1}x^{(p-1)P}$,
then we note that $e^{2\pi i/p}$ is a root of $a_0 + a_1x + \cdots + a_{n-1}x^{p-1}$,
from which it follows that $\Phi(x)\, | \, a_0 + a_1x + \cdots + a_{n-1}x^{p-1}$.} 
of $\Phi_p(x) = 1 + x + \cdots + x^{p-1}$,
as desired. 

For the other direction, assume that Conjecture \ref{conj} holds for $n$.
Let $B$ be a matrix whose rows span $V_n^\perp$, and let $A$ be obtained
by truncating the last $P - 1$ columns of $B$.
We note the rows of $A$ are vectors in $\rr^{n-P+1} = \rr^{\mH\,\cup\,\F^+}$.
%Let $A$ be a matrix whose rows span the restriction of $V_n^\perp$ to
%$\rr^{n-P+1} = \rr^{\mH\,\cup\,\F^+}$ (e.g., take a basis of $V_n^\perp$, drop
%the last $P - 1$ entries of each vector, and let the resulting vectors
%be the rows of $A$). 
There is no vector $x \in \rr^{\mH\,\cup\,\F^+}$, $x \geq 0$,
such that $Ax = 0$ and such that $x_j > 0$ for some $j \in \F^+$
%nonzero on $\F^+$ 
(otherwise extending $x$ to $\rr^n$ with 0's would produce a vector $\ov{x} \geq 0$
nonzero on $\F^+$
such that $B\ov{x} = 0$ %and such that $\ov{x}$ is nonzero on $\F^+$
and $\ov{x}$ is zero on $\F^-$, contradicting Conjecture \ref{conj}).
%contradicting the conjecture.
By Proposition \ref{farkie} this implies there is a vector $y$
such that $y^TA \geq 0$ and such that $y^TA$ is positive on $\F^+$. 
Moreover, $y^TA$ must be 0 on $\mH$ because 
$(y^TA)1_{\mH} = y^T(A1_{\mH}) = 0$
(where we view $1_{\mH}$ as a vector in $\rr^{\mH\,\cup\,\F^+}$).
Thus $y^TB$ is a vector in $V_n^\perp$
that is positive on $\F^+$ and zero on $\mH$, as desired.
\end{proof}

\noindent
We call the vector $w$ satisfying the conditions of Lemma \ref{basiclem}
a \emph{certificate}. We point out the obvious fact that Lemma \ref{basiclem}
gives a means of disproving Conjecture \ref{conj} without actually exhibiting
a counterexample polynomial divisible by $\Phi_n(x)$ (namely, it sufficies to
show that the constraints on $w$ determine an empty polytope in $\rr^n$).
%rational polytope determined by the constraints on $w$ is empty).
However, from a computational standpoint, this method is not necessarily
faster than directly seeking a counterexample polynomial (which reduces to
showing non-emptiness of a certain polytope in $\rr^n$, or in $\rr^{\mH\,\cup\,\F^+}$).

We note that if one is only interested in showing
that the smallest degree of a polynomial with nonnegative coefficients
divisible by $\Phi_n(x)$ is at least $(p-1)n/p = n - P$ (without proving
uniqueness), then a weaker type of certificate suffices, as given by the
following lemma.

\begin{lemma}\label{weakerlem}
$V_n$ ($n$ squarefree) contains no nonzero, nonnegative vector that is zero on $\F^- \cup \{n-P\}$ if and
only if there exists a $w \in V_n^\perp$ such that $w$ is positive outside $\F^- \cup \{n-P\}$.
\end{lemma}

\noindent
The proof of Lemma \ref{weakerlem} is similar to the proof of Lemma \ref{basiclem}.
We omit it because we will not use Lemma \ref{weakerlem}.

To apply Lemma \ref{basiclem} (by finding a certificate) 
we need some understanding of $V_n^\perp$. 
Thankfully $V_n^{\perp}$ has a relatively simple structure 
(first investigated by R\'edei \cite{redei3} and deBruijn \cite{bruijn3} and 
also later by Conway and Jones \cite{conway}), outlined below.

Let $G_0(x) = 1 + x^P + \cdots + x^{(p-1)P}$ and let $G_i(x) = 1 + x^{Q_i} + \cdots + x^{(q_i - 1)Q_i}$ for $i \geq 1$ (recall that $Q_i = n/q_i$). It is easy to check by examining the roots of $G_0(x), \ldots, G_k(x)$ that $\Phi_n(x) = \gcd(G_0(x), \ldots, G_k(x))$. Therefore $V_n$ is spanned by the coefficient vectors of all the translates\footnote{By \emph{translate} of a polynomial $p(x)$ we mean a polynomial of the form $x^kp(x)$.} of degree at most $n - 1$ of the polynomials $G_0(x), \ldots, G_k(x)$. (As a sidenote, since the vanishing sums of roots of unity corresponding to $G_0(x), \ldots, G_k(x)$ are regular $q$-gons with $q = p,q_1,\ldots,q_k$ it follows from the above observation that every vanishing sum of $n$-th roots of unity can be obtained as a linear combination of regular $q$-gons with $q | n$. If any vanishing sum of $n$-th roots of unity with nonnegative coefficients could be obtained as a \emph{nonnegative} linear combination of regular $q$-gons then Conjecture \ref{conj} would follow immediately, since the $q$-gon with the lowest highest power of $\zeta_n$ is the $p$-gon. This is true when $n$ has only 2 prime factors by deBruijn's Theorem \cite{bruijn3} but is not the case in general. Schoenberg \cite{schoenberg} pointed out the first counterexample (for $n = 30$) and others have followed suit \cite{mann,conway,bjorn,lamleung,meisminimal}.)

We now identify vectors in $V_n$ with $(k+1)$-dimensional arrays of real numbers of size $p \times q_1 \times \cdots \times q_k$ using the Chinese Remainder Theorem (CRT). Under this mapping, the array entry with coordinate $(t_0, \ldots, t_k)$---where array coordinates are indexed from 0, like vector indices---is mapped to the vector entry with index $t_0P + t_1Q_1 + \ldots + t_kQ_k \mod n$ (Figs$.$ \ref{firstF} and \ref{bigCRT} show such maps for $n = 5\cdot 7$ and $n = 3\cdot 5 \cdot 7$), and we say that $t_0P + t_1Q_1 + \ldots + t_kQ_k \mod n$ is the \emph{index} of the entry $(t_0, \ldots, t_k)$. This mapping is a bijection, so there is a one-to-one correspondence between vectors in $\rr^n$ and arrays of size  $p \times q_1 \times \cdots \times q_k$.

Our reason for representing vectors in $V_n$ as arrays is that the generators for $V_n$ described above---the coefficient vectors of the translates of $G_0(x)$, $\ldots$, $G_k(x)$---correspond to particularly simple arrays. The coefficient vector of $G_0(x) =  1 + x^P + \cdots + x^{(p-1)P}$ maps to the 0-1 array whose nonzero entries are $\{(h,0,\ldots,0):0\leq h \leq p-1\}$. %(where array coordinates start from 0). 
Thus the array corresponding to $G_0(x)$ consists of a ``line of 1's'' in the direction of the first coordinate axis. The translates of $G_0(x)$ of degree $\leq n-1$ map to all the parrallel lines of 1's in that direction. Similarly the translates of $G_1(x)$, $\ldots$, $G_k(x)$ map to all lines of 1's in the remaining coordinate directions, so that $V_n$ is precisely the set of arrays that are generated as linear combinations of lines of 1's in all the coordinate directions.

We will refer to the lines of 1's as \emph{fibers} (to be perfectly clear: for an array of size $a_1 \times \dots \times a_k$, a fiber is a 0-1 array whose support is $\{(x_1,\ldots,h,\ldots,x_k):0\leq h \leq a_i-1\}$ where $h$ is in the $i$-th coordinate place and where $x_1$, $\ldots$, $x_{i-1}$, $x_{i+1}$, $\ldots$, $x_k$ are constant, for some $i$). In other papers \cite{meisminimal, dcstein} we have dubbed arrays (of any size) which, like $V_n$, are linear combinations of fibers, as \emph{cyclotomic arrays}. Cyclotomic arrays have a number of interesting combinatorial properties. For example, the sum of the entries of any nonnegative, integer-valued cyclotomic array is always a nonnegative integer linear combination of its sidelengths \cite{dcstein}, generalizing a property of vanishing sums of roots of unity \cite{lamleung}.

%Note that under this map an array consisting of a single line of 1's running parallel to the $j$-th coordinate axis maps to the coefficient vector of $x^zG_j(x)$ for some $z$. Therefore $V_n$, when viewed as a set of arrays, is spanned by arrays consisting of a single line of 1's running parallel to one of the coordinate axes. We call these types of arrays \emph{fibers}. (An array of any size spanned by fibers is known as a \emph{cyclotomic array}. Cyclotomic arrays generalize a number of interesting properties of vanishing sums of roots of unity \cite{meisminimal, dcstein}.)

Knowing that $V_n$ is spanned by fibers makes clear the structure of $V_n^\perp$: points in $V_n^\perp$ are exactly those arrays of size $p \times q_1 \times \cdots \times p_k$ whose column sums are zero for all columns in every direction, since the column sums of an array are zero if and only if the dot product of that array with all fibers is zero. We call an array with zero column sums in every direction a \emph{zero-sum} array. 
%The number associated to each array coordinate under the CRT mapping will be called the \emph{index} of the coordinate. 
Our blueprint for proving Theorem \ref{main} 
is thus to exhibit a zero-sum array $w$ (the ``certificate'') that 
is positive on entries whose index is in $\F^+$
and zero on entries whose index is in $\mH$. In other words,
$w$ is positive on entries of index less than $n - P$ 
except for entries whose index is 0 mod $P$, on which $w$ is zero.

\firstFigure

\section{Low-Dimensional Examples}\label{sec:lowdim}

%To illustrate our method we will use it to 

In this section we use the strategy outlined above to prove Conjecture \ref{conj} for the two-prime case $n = 35$ and the three-prime case $n = 105$. We start with $n = 35$. Since $35$ is a product of two primes this case already follows from deBruijn's theorem \cite{bruijn3}, but the point is to illustrate our method.

The left of Fig$.$ \ref{firstF} shows the mapping from arrays of size $5 \times 7$ to $\rr^{35}$ given by our application of the CRT. A ``layer'' of the array refers to a horizontal row of 7 cells. On the right of Fig$.$ \ref{firstF} the array cells have been partitioned into $\mH$, $\F_0$, $\ldots$, $\F_4$ according to their index, using the same definitions for $\mH$, $\F_0, \ldots, \F_{p-1}$ as in Section \ref{sec:methods}. We also define $\F^+ = \F_0 \cup \cdots \cup \F_{p-2} = \F_0 \cup \F_1 \cup \F_2 \cup \F_3$ and $\F^- = \F_4$.

We wish, thus, to find a $5 \times 7$ zero-sum array $w$ that is zero on $\mH$ and positive on $\F^+$. Note that since every column besides the first contains exactly one entry from $\F^- = \F_4$, $w$ must be negative on $\F^-$ in order for column sums to be zero. The $\F_i$'s are translates of each other because going up a layer adds $P$ mod $n$ to the index of an entry. As a consequence the $\F_i$'s induce an identical partition of each layer.

\signPatternsWsFigure

We construct our array $w$ as a linear combination of $5 \times 7$ zero-sum arrays $w_1, w_2, w_3, w_4$ such that $w_i$ is negative on $\F_i$, positive on $\F_{i-1} \cup \F_{i+1}$ and 0 elsewhere (indices referring to elements in the set $\{0, 1, \ldots, 4\}$ are taken mod 5). The signs of $w_1, \ldots, w_4$ are sketched in Fig$.$ \ref{signWs}. Then if $\alpha_2$, $\alpha_3$, $\alpha_4$ are taken sufficiently quickly increasing the array $w = w_1 + \alpha_2w_2 + \alpha_3w_3 + \alpha_4w_4$ will be zero-sum, positive on $\F_0 \cup \cdots \cup \F_3$ and 0 on $\mH$, as desired. Note $w_2$, $w_3$, $w_4$ can be obtained from $w_1$ by shifting $w_1$ up by respectively 1, 2 or 3 layers cyclically, so it suffices to construct $w_1$.

\signPatternsAsFigure

We build $w_1$ as the sum of 5 zero-sum arrays $a_0, \ldots, a_4$ where $a_i$ is negative on the intersection of layers $i$, $i+1$ with $\F_1$ and positive on the intersection of layers $i$, $i+1$ with respectively $\F_0$ and $\F_2$, and 0 elsewhere. The sign patterns for $a_0, \ldots, a_4$ are sketched in Fig$.$ \ref{signAs}. Such arrays $a_0, \ldots, a_4$ obviously exist. Setting $w_1 = a_0 + \dots + a_4$ we obtain a zero-sum array that is negative on $\F_1$, positive on $\F_0 \cup \F_2$ and 0 elsewhere, as desired. This completes the construction.

\bigCRTFigure

\bigPartitionFigure

Now let $n = 105 = 3\cdot 5\cdot 7$. In this case $p = 3$, $q_1 = 5$, $q_2  = 7$ and $P = n/p = 35$, $Q_1 = n/q_1 = 21$, $Q_2 = n/q_2 = 15$. Fig$.$ \ref{bigCRT} shows the CRT mapping from the $3 \times 5 \times 7$ array to $\zz_{105}$.
 %given by sending entry $(j_1,j_2,j_3)$ to $j_1P + j_2Q_1 + j_3Q_3$ mod $n$. %As usual the ``index'' of an entry $(j_1,j_2,j_3)$ is its value under this mapping. 
A ``layer'' of the array again means a layer perpendicular to the smallest coordinate direction, so there are 3 layers each consisting of an array of size $5 \times 7$. Subscripts referring to values in the sets $\zz_3 = \{0,1,2\}$, $\zz_5 = \{0,1,\ldots,4\}$ or $\zz_7 = \{0,1,\ldots,6\}$ are taken mod 3, 5 and 7 respectively.

%We now try to carry out a similar procedure when $n = pq_1q_2$ has 3 prime factors. This will be our first case not covered by any previous results. Say $p = 3$, $q_1 = 5$, $q_2  = 7$, so $n = 105$. Let $P = n/p = 35$, $Q_1 = n/q_1 = 21$, $Q_2 = n/q_2 = 15$. 

%We again partition the array entries into families $\mH$, $\F_0$, $\ldots$, $\F_{p-1}$ where $\mH$ contains the entries of index 0 mod $P$ and $\F_i$ contains the entries whose index lies between $iP$ and $(i+1)P$. 

The partition of the array cells into the sets $\mH, \F_0, \ldots, \F_{p-1}$ is shown in Fig$.$ \ref{bigPartition}. Note that the $\F_i$'s again induce an identical partitioning of each layer, for the same reason that going up one layer increases the index of an entry by $P$ mod $n$. Again, we wish to construct a zero-sum array $w$ which is 0 on $\mH$ and positive on $\F^+ = \F_0 \cup \ldots \cup \F_{p-1} = \F_0 \cup \F_1$. We can note that if $w$ exists it will be negative on $\F^- = \F_2$ for the column sums of length 3 to be zero.

\wOneSupFig

We construct $w$ as a linear combination of $p - 1 = 2$ zero-sum arrays $w_1$, $w_2$ where $w_i$ is negative on $\F_i$ and positive on $\F_{i-1} \cup \F_{i+1}$ and zero elsewhere. The sign pattern of $w_1$ is sketched in Fig$.$ \ref{wOneBig}. Then if we take $\alpha > 0$ sufficiently large $w = w_1 + \alpha w_2$ will be a zero-sum array positive on $\F_0 \cup \F_1$, negative on $\F_2$ and 0 on $\mH$, as desired. Note that $w_2$ can be obtained by shifting $w_1$ up by one layer cyclically so it suffices to construct $w_1$. (This example with $p = 3$ is a little unfortunate since one could directly take $w = w_2$; a better example would have had $p = 5$, but would have been harder to draw.)

\AZeroFig

We build $w_1$ as the sum of $p = 3$ zero-sum arrays $a_0, a_1, a_2$ where $a_i$ is negative on the intersection of layers $i$, $i+1$ with $\F_1$, positive on the intersection of layers $i$, $i+1$ with respectively $\F_0$ and $\F_2$, and 0 elsewhere. The sign pattern for $a_0$ is sketched in Fig$.$ \ref{AZero}. The sum $a_0 + a_1 + a_2$ is negative on $\F_1$, positive on $\F_0 \cup \F_2$ and 0 elsewhere (namely on $\mH$), as desired. The reader can compare Figs$.$ \ref{signAs} and \ref{AZero}. In particular, note that the support of $a_i$ is each time contained in two layers of opposite sign. %, and that these layers must be negative of one another because of the zero-sum condition.

Because $a_i$ is a zero-sum array the layers $i$ and $i+1$ of $a_i$ must be negative of one another (other layers being 0). Thus to determine $a_i$ we only need to determine the $i$-th layer of $a_i$, which must be positive on $\F_0$, negative on $\F_1$, zero elsewhere and have zero column sums in the two coordinate directions. We illustrate how to do this for $a_0$, in which case the problem is to construct a $5 \times 7$ zero-sum array $u_0$ having the positive and negative supports of the leftmost $5 \times 7$ array in Fig$.$ \ref{AZero}.

We now describe the construction of $u_0$, sketched in Fig$.$ \ref{bfone}. We found it useful to ``unroll'' the torus $\zz_5 \times \zz_7$ onto $\zz \times \zz$. Let 
%$\G_0 = \{(j_1,j_2) \in \zz_5 \times \zz_7: (0,j_1,j_2) \in \F_0\} = \{(j_1,j_2) \in \zz_5 \times \zz_7: 0 < j_1Q_1 + j_2Q_2\!\mod n < P\}$, 
%$\G_1 = \{(j_1,j_2) \in \zz_5 \times \zz_7: (0,j_1,j_2) \in \F_1\} = \{(j_1,j_2) \in \zz_5 \times \zz_7: P < j_1Q_1 + j_2Q_2\!\mod n < 2P\}$. 
$\G_0 = \{(j_1,j_2) \in \zz_5 \times \zz_7: (0,j_1,j_2) \in \F_0\}$,
$\G_1 = \{(j_1,j_2) \in \zz_5 \times \zz_7: (0,j_1,j_2) \in \F_1\}$.
(Thus $\G_0$ and $\G_1$ are respectively the positive and negative supports of $u_0$.) 
Let $z = (Q_1, Q_2) = (21, 15) \in \zz^2$ and let 
$\G_0' = \{x \in \zz^2 : 0 < \langle x, z \rangle < P\}$, $\G_1' = \{x \in \zz^2 : P < \langle x, z \rangle < 2P\}$. 
Let $\rho : \zz^2 \ra \zz_5 \times \zz_7$ be the projection map $\rho(j_1,j_2) = (j_1 \!\mod 5, j_2 \!\mod 7)$.
It is easy to see
that 
$\rho(\G_0') = \G_0$, $\rho(\G_1') = \G_1$ from the definition of $\F_0$, $\F_1$. 

% where $\rho : \zz^2 \ra \zz$ is the projection map $\rho(j_1,j_2) = (j_1 \!\mod 5, j_2 \!\mod 7)$. 

Note that $\rho(x) = \rho(y) \implies \langle x, z \rangle - \langle y, z \rangle \equiv 0 \mod n$, but if $x, y \in \G'_0 \cup \G'_{1}$ then $|\langle x, y \rangle - \langle y, z \rangle| < 2P \leq n$ so $\rho(x) = \rho(y) \implies \langle x, z \rangle = \langle y, z \rangle$ for $x, y \in \G'_0 \cup \G'_{1}$. Thus if $f: \zz^2 \rightarrow \rr$ is a function with support $\G'_0 \cup \G'_{1}$ such that $\langle x, z \rangle = \langle y, z \rangle \implies f(x) = f(y)$ there is a well-defined $5 \times 7$ array $u_f$ with support $\G_0 \cup \G_1$ whose $\rho(x)$-th
% whose $(j_1,\ldots,j_k)$-th 
entry has value $f(x)$ for any $x \in \G'_0 \cup \G'_{1}$. A function $f$ such that $\langle x, z \rangle = \langle y, z \rangle \implies f(x) = f(y)$ will be called \emph{periodic}. 

A \emph{line of integers} is a subset of $\zz^2$ of the form $\{(x,y):x \in \zz\}$ for some $y \in \zz$ or $\{(x,y): y\in \zz\}$ for some $x \in \zz$. We say that $f$ is \emph{zero-sum} if its support is finite on every line of integers and sums to zero on every line of integers.
%sum on every line of integers converges absolutely to zero (issues of convergence are trivial when the support within each line is finite, as it will be in our case). %Since $\rho$ is injective on the intersection of any line of integers with $\G_0' \cup \G_1'$ (because $0 < |\langle x, z \rangle - \langle y, z \rangle| < n$ implies $\rho(x) \ne \rho(y)$ for all $x, y \in \zz^2$) 
It is clear that if $f$ is periodic and has support $\G_0' \cup \G_1'$ then $u_f$ is zero-sum if $f$ is zero-sum. 
%It is clear that a zero-sum periodic function $f$ in $\zz^2$ with support in $\G_0'\cup \G_1'$ defines a zero-sum $5 \times 7$ array $u_f$ with support $\G_0 \cup \G_1$. 
Thus the construction of $u_0$ reduces to exhibiting a periodic zero-sum function $f$ on $\zz^2$ that is positive on $\G_0'$, negative on $\G_1'$ and zero elsewhere.

\bigfigone

Fig$.$ \ref{bfone} shows our method for constructing such a function
$f$. First we consider $\zz^2$ as a subset of $\rr^2$ the natural
way. The square $[i-\frac{1}{2},i+\frac{1}{2}]\times
[j-\frac{1}{2},j+\frac{1}{2}]$ centered at a point $(i,j) \in \zz^2$
is called the \emph{cell around $(i,j)$} or \emph{cell centered at
  $(i,j)$}, and if $\mc{A}$ is any subset of $\zz^2$ we write
$\ov{\mc{A}}$ for the union of all cells centered at points in
$\mc{A}$. Let $L_2$ be the line $\{(x,y): \langle (x, y), z \rangle =
P\} \subseteq \rr^2$ and let $L_1$, $L_3$ be two translates of $L_2$ equidistant from $L_2$ such that (i) $L_1$ and $L_3$ are contained in $\ov{\G_0' \cup \G_1'}$, and (ii) the region between $L_1$ and $L_2$ (resp.~$L_3$ and $L_2$) intersects every cell in $\ov{\G_0'}$ (resp.~$\ov{\G_1'}$) in a nonzero area. The existence of $L_1$, $L_2$, $L_3$ is clear from Fig$.$ \ref{bfone} and is formally proved in the next section.

Let $R^+$ be the region between $L_1$ and $L_2$ and $R^-$ the region between $L_2$ and $L_3$. We define 
$$f(x) = \vol(\ov{x} \cap R^+) - \vol(\ov{x} \cap R^-)$$ 
where $\ov{x} = \ov{\{x\}}$ is the cell around $x \in \zz^2$ and $\vol(\cdot)$ is two-dimensional area. Then the support of $f$ is contained in $\G_0' \cup \G_1'$ because cells not in $\ov{\G_0'\cup\G_1'}$ have no area in $R^+ \cup R^-$, and $f$ is zero-sum because if $\mL$ is any line of integers,
$$
\sum_{x\in\mL}f(x) = \vol(\Lbar \cap R^+) - \vol(\Lbar \cap R^-) = 0
$$
as $R^+$, $R^-$ have equal thickness. Moreover $f(x)$ is positive on $\G_0'$ and negative on $\G_1'$, since points in $\G_0'$ are below $L_2$ and points in $\G_1'$ and since every cell in $\ov{\G_0' \cup \G_1'}$ intersects $R^+ \cup R^-$ in a nonzero area (point (ii) above).
Finally $f$ is periodic since $L_1$, $L_2$, $L_3$ are perpendicular to $z$. 

This concludes the construction of $u_0$, and hence of $a_0$. (One can also construct $u_0$ by other, non-geometric approaches, but the geometric method is the only one we found to generalize to higher dimensions (higher numbers of primes).)

\bigfigtwo

The remainder of the construction rests on making $5 \times 7$ zero sum arrays $u_1$ and $u_2$ whose positive and negative supports are respectively $\G_1$ and $\G_2$ (for $u_1$) and $\G_2$ and $\G_0$ (for $u_2$), where $\G_2 = \{(j_1,j_2) \in \zz_5 \times \zz_7: (0,j_1,j_2) \in \F_2\}$. The arrays $u_1$, $u_2$ can be found with the same method as $u_0$, though the construction of $u_2$ presents a difference which is worth mentioning. Fig$.$ \ref{bftwo} shows the analog of Fig$.$ \ref{bfone} for the construction of $u_2$; here $\G_2' = \{x\in\zz^2:2P < \langle x, z \rangle < 3P\}$, so $\rho(\G_2') = \G_2$, and $\G_3' = \{x\in\zz^2:3P < \langle x, z \rangle < 4P\}$ is a translate of $\G_0'$ by $(q_1, 0)$ (or $(0,q_2)$), so $\rho(\G_3') = \rho(\G_0') = \G_0$
(we cannot use $\G_0'$ and $\G_2'$ because $\ov{\G_0'}$ and $\ov{\G_2'}$ are non-contiguous regions). In this case the region $\ov{\G_2' \cup \G_3'}$ is not simply connected. The ``embedded'' blank cells correspond to integer points on the line $L_2 = \{x : \langle x, z \rangle = 3P = n\}$, which are preimages of $(0,0) \in \zz_5 \times \zz_7$ under $\rho$ (by contrast, the lines $\langle x, z \rangle = P$ and $\langle x, z \rangle = 2P$ contain no integer points, as the gcd of the coordinates in $z$ does not divide $P$ or $2P$) (also note that $(0,0) \in \zz_5 \times \zz_7$ is the set $\{(j_1,j_2) \in \zz_5 \times \zz_7 : (0, j_1, j_2) \in \mH \}$). However $f$ remains zero on the integer points in $L_2$ since the cells centered at these points have equal areas in $R^+$ and $R^-$, thus maintaining the correctness of the support.

This concludes the discussion of the cases $n = 35$ and $n = 105$. 
In higher dimensions
%(i.e.~for higher number of primes in the factorization of $n$) 
(i.e.~for $n$ with more prime factors)
an obstacle which arises is that
the shaded region is too ``thin'' to contain a hyperplane;
then $L_1$, $L_2$ and $L_3$ (which are hyperplanes in the general case)
cannot be embedded in the shaded region,
and the whole approach breaks down. 
In fact, the condition
$2/p > 1/q_1 + \cdots + 1/q_k$ from Theorem \ref{main} guarantees
that the shaded region is ``thick enough'' to accomodate the
sandwich of hyperplanes $L_1$, $L_2$, $L_3$.
Moreover, in the general case and when $n$ is a product of many
large distinct primes, 
the region $\F_{p-1}$ itself becomes a precariously thin
slice of the whole array, and the union of the cells
in $\F_{p-1}$ becomes very far from containing a hyperplane. 
This causes us to be pessimistic that the certificate $w$ always
exists, and hence that Conjecture \ref{conj} holds.
This pessimism is reinforced by the fact that the constraints
on $w$ for the case $n = pq_1\cdots q_k$ are a strict subset of those
for the case $n = pq_1\cdots q_kq_{k+1}$, where $q_{k+1} > p$ can be any
prime distinct from $q_1, \ldots, q_k$. 
(The latter fact is not surprising considering that
Conjecture \ref{conj} for $n = pq_1\cdots q_k$ is implied by
Conjecture \ref{conj} for $n = pq_1\cdots q_{k+1}$.)
See also the comments after Problem \ref{theprob} below.
Appending primes \emph{ad infinitum} also leads us to
consider the existence of an ``infinite certificate'' for a given
prime $p$. Such an infinite certificate would be, more precisely, an
infinite array $w_p$ of size 
$p \times q_1 \times q_2 \times q_3 \times \cdots$ where $q_1$, $q_2$,
$q_3, \ldots$ enumerate the primes greater than $p$, 
where for each $k$ the restriction of $w_p$ to entries
that have $\ell$-th coordinate 0 for $\ell > k+1$
constitutes a certificate %that Conjecture \ref{conj} holds
for the case $n = pq_1\cdots q_k$. For example, we know \emph{finite}
certificates\footnote{We know these finite certificates exist because
  Theorem \ref{conj} is true for even $n$ by physical considerations;
  it would indeed be interesting to find combinatorial and/or algebraic
  constructions (or merely proofs of existence) for these certificates.} 
of all sizes exist for $p = 2$ by Theorem \ref{conj}, but
it is not obvious whether these finite certificates can be extended to
an infinite array $w_2$ as just described. We leave this as another interesting open problem.

\ignore{
If we keep on appending primes, and if Conjecture
\ref{conj} is true, we are led to conclude (by compactness)
the existence, for every
prime $p$, of an infinite array $w_p$ of size 
$p \times q_1 \times q_2 \times q_3 \times \cdots$ where $q_1$, $q_2$,
$q_3, \ldots$ enumerate the primes greater than $p$, 
where for each $k$ the restriction of $w_p$ to entries
that have $\ell$-th coordinate 0 for $\ell > k+1$
constitutes a certificate %that Conjecture \ref{conj} holds
for the case $n = pq_1\cdots q_k$. (This throws back to the non-finite
case of Conjecture \ref{conj} discussed at the end of the introduction.)
Such an array $w_p$ has the trappings, in our eyes, of 
a combinatorial object that is ``too good to be true''. 
%whence our reticence to believe Conjecture \ref{conj}.
On the other hand the infinite array
$w_p$ \emph{does} exist for $p = 2$, as noted\footnote{Theorem
  \ref{main} dispatches the case $p = 2$ using the physical
  considerations of a balanced plate and, indeed, it would be nice if
  some explicit construction of $w_p$ could be given for $p = 2$
  or, alternatively, if the ``physical'' proof of $w_p$'s existence
  for $p = 2$ could be
  replaced by a combinatorial and/or algebraic proof of existence.} by Theorem \ref{main},
which could be seen as giving credence to the opposite belief.
We also refer to the comments after Problem \ref{theprob} below.
}

\section{The General Case}

Take $n = pq_1\cdots q_k$ with $p < q_1, \ldots, q_k$. As before we work with arrays of size $p \times q_1 \times \cdots \times p_k$ where the index of entry $(j_0, j_1, \ldots, j_k)$ is $j_0P + j_1Q_1 + \cdots + j_kQ_k \mod n$, where $P = n/p$ and $Q_i = n/q_i$. 
As before, $\mH$ is the set of entries of index 0 mod $P$ and $\F_i$ is the set of 
entries whose index is greater than $iP$ but less than $(i+1)P$, $0 \leq i \leq p-1$. 
By Lemma \ref{basiclem} it is sufficient to construct a zero-sum array $w$ of 
size $p \times q_1 \times \cdots \times q_k$ which is zero on $\mH$ and positive on $\F^+ = \F_0 \cup \cdots \cup \F_{p-2}$. 
A ``layer'' of the array is an array of size $q_1 \times \cdots \times q_k$ obtained by fixing a 
value for the first coordinate (so there are $p$ layers). 
We note that the sets $\F_i$ induce identical partitions of every layer 
because the index of an entry increases by $P$ mod $n$ as we go up one layer, 
i$.$e$.$ if an entry is in $\F_i$ then the entry whose first coordinate 
is one greater is in $\F_{i+1}$ (as usual indices refering to numbers in $\{0,\ldots,p-1\}$ are taken mod $p$).

We construct $w$ as a linear combination of zero-sum arrays $w_1, \ldots, w_{p-1}$ such that each $w_i$ is negative on $\F_i$, positive on $\F_{i+1} \cup \F_{i-1}$ and zero elsewhere. Then if $\alpha_2, \ldots, \alpha_{p-1} > 0$ are taken sufficiently quickly increasing $w = w_1 + \alpha_2w_2 + \cdots + \alpha_{p-1}w_{p-1}$ is negative only on $\F_{p-1}$ and positive everywhere else except on $\mH$, where it is 0. Because $(j_0, j_1, \ldots, j_k) \in \F_i \implies (j_0+1, j_1, \ldots, j_k) \in \F_{i+1}$ it is sufficient to construct the array $w_1$, as $w_2, \ldots, w_{p-1}$ can be obtained from $w_1$ by translation.

We construct $w_1$ as a sum of zero-sum arrays $a_0, \ldots, a_{p-1}$ where $a_i$ is negative on the intersection of layers $i$, $i+1$ with $\F_1$ and positive on the intersection of layers $i$, $i+1$ with respectively $\F_0$ and $\F_2$. Let $\G_i = \{(j_1, \ldots, j_k): (0,j_1,\ldots,j_k) \in \F_i\}$. Considering layer $i$ as a standalone $q_1 \times \cdots \times q_k$ array, the positive support of $a_i$ in layer $i$ is $\{(j_1,\ldots,j_k): (i,j_1,\ldots,j_k) \in \F_0\} = \{(j_1,\ldots,j_k): (0,j_1,\ldots,j_k) \in \F_{-i} = \F_{p-i}\} = \G_{p-i}$ and the negative support of $a_i$ in layer $i$ is $\{(j_1,\ldots,j_k): (i,j_1,\ldots,j_k) \in \F_1\} = \{(j_1,\ldots,j_k): (0,j_1,\ldots,j_k) \in \F_{1-i} = \F_{p-i+1}\} = \G_{p-i+1}$.
Therefore in order to construct $a_i$ it is sufficient to construct a zero-sum $q_1 \times \cdots \times q_k$ array $u_{p-i}$ which is positive on $\G_{p-i}$, negative on $\G_{p-i+1}$ and zero elsewhere. Then $a_i$ can be obtained by placing $u_{p-i}$ at layer $i$ and $-u_{p-i}$ at layer $i + 1$. Thus the construction of $w_1$ reduces to the construction of zero-sum arrays $u_0, \ldots, u_{p-1}$ of size $q_1 \times \cdots \times q_k$ such that $u_i$ is positive on $\G_i$, negative on $\G_{i+1}$ and zero elsewhere.

The problem of constructing the $u_i$'s can be rephrased in $\zz^k$. Let $z = (Q_1,\ldots,Q_k) \in \zz^{k}$ and let $\G_i' = \{x \in \zz^k: iP < \langle x, z \rangle < (i+1)P\}$ for $0 \leq i \leq p$. Let $\rho: \zz^k \rightarrow \zz_{q_1} \times \cdots \times \zz_{q_k}$ be the projection defined by $\rho(x_1,\ldots,x_k) = (x_1 \!\mod q_1, \ldots, x_k \!\mod q_k)$. As before, $\rho(\G'_i) = \G_i$ (and $\rho(\G'_{p}) = \G_{0}$). Moreover $\rho(x) = \rho(y) \implies \langle x, z \rangle - \langle y, z \rangle \equiv 0 \mod n$, but if $x, y \in \G'_i \cup \G'_{i+1}$ then $|\langle x, y \rangle - \langle y, z \rangle| < 2P \leq n$ so $\rho(x) = \rho(y) \implies \langle x, z \rangle = \langle y, z \rangle$ for $x, y \in \G'_i \cup \G'_{i+1}$. Thus if $f: \zz^k \rightarrow \rr$ is a function with support $\G'_i \cup \G'_{i+1}$ such that $\langle x, z \rangle = \langle y, z \rangle \implies f(x) = f(y)$ there is a well-defined $q_1 \times \cdots \times q_k$ array $u_f$ whose $(j_1,\ldots,j_k)$-th entry has value $f(x)$ for any $x \in \G'_i \cup \G'_{i+1}$ with $\rho(x) = (j_1,\ldots,j_k)$ or has value 0 if $(j_1,\ldots,j_k) \notin \rho(\G'_i \cup \G'_{i+1}) = \G_i \cup \G_{i+1}$, for all $0 \leq i \leq p-1$.

A \emph{line of integers} is a set of the form $\{(c_1,\ldots,c_{j-1},x_j,c_{j+1},\ldots,c_k): x_j \in \zz\}$ where the $c_i$'s are integer constants, for any $j \in \{1,\ldots,k\}$.
A function $f$ on $\zz^k$ is a \emph{zero-sum} function if its support is finite on every line of integers and sums to zero on every line of integers. If $f_i: \zz^k \rightarrow \rr$ is a zero-sum function that is positive on $\G'_i$, negative on $\G'_{i+1}$, zero elsewhere and such that $\langle x, z \rangle = \langle y, z \rangle \implies f(x) = f(y)$ then it is straightforward to check that $u_{f_i}$ is a zero-sum array that is positive on $\G_i$, negative on $\G_{i+1}$ and zero elsewhere and one may therefore take $u_i = u_{f_i}$. Conjecture \ref{conj} thus reduces to an instance of the following more general problem:

\begin{problem}\label{theprob}
Let $P > Q_1, \ldots, Q_k$ be positive rationals and let $z = (Q_1, \ldots, Q_k)$. Let $h \in \rr$ and let $\G^+ = \{x \in \zz^k: h - P < \langle x, z \rangle < h\}$, $\G^- = \{x \in \zz^k: h < \langle x, z \rangle < h + P\}$. Find a zero-sum function $f$ on $\zz^k$ such that $\langle x, z \rangle = \langle y, z \rangle \implies f(x) = f(y)$ and that is positive on $\G^+$, negative on $\G^-$ and zero elsewhere.
\end{problem}

\noindent Note that if some line of integers contains a point 
in $\G^+$ but no point in $\G^-$ or vice-versa then Problem \ref{theprob} 
has no solution. The condition $P > Q_1, \ldots, Q_k$, however, precludes this, 
as translating $x$ by one unit in the $i$-th coordinate direction increases $\langle x, z \rangle$ by $Q_i < P$. 
We also note that an argument using averaging and compactness shows that
the condition  $\langle x, z \rangle = \langle y, z \rangle \implies f(x) = f(y)$ is
without loss of generality: if $f$ exists without this condition, there also
exists an $f$ that satisfies this condition. Hence this condition can be
included for free.

%We note that an argument using averaging and compactness can be used to show


%As stated, $P, Q_1, \ldots, Q_k$


Problem \ref{theprob} is trivial for $k = 1$ and can be solved by combinatorial methods for $k = 2$, but is seemingly very hard for $k \geq 3$. Moreover since all the constraints of a $k$-dimensional instance of the problem can be strictly contained\footnote{This is indeed reminiscent of Conjecture \ref{conj} itself. (We are alluding
to the fact that the case $n = m$ of Conjecture \ref{conj} is implied by the case $n = mq$ for any prime $q$ larger than the smallest prime dividing $m$.)} 
in a $(k+1)$-dimensional instance of the problem, there seems to be no ``good reason'' why Problem \ref{theprob} should always have a solution, 
%\footnote{This is reminiscent of Conjecture \ref{conj} itself, where the case $n = m$ is implied by the case $n = mq$, where $q$ is any prime not smaller than the smallest prime dividing $m$, cf. the non-finite case of Conjecture \ref{conj} discussed at the end of the introduction.}
and indeed it does not. 
Small sets of parameters for which Problem \ref{theprob} doesn't have a solution are, for example,
obtained by putting $k = 3$, $h = 0$, $P = n/p$, $Q_1 = n/q_1$, $Q_2 = n/q_2$, $Q_3 = n/q_3$, $n = pq_1q_2q_3$ with either
$$
(p, q_1, q_2, q_3) = (6, 7, 8, 9)
$$ 
or 
$$
(p, q_2, q_2, q_3) = (11, 13, 17, 19).
$$
The latter setting of parameters is in fact derived from the smallest value of $n$ not covered by
Theorem \ref{main}, being $n = 46189 = 11\cdot 13\cdot 17\cdot 19$.
These negative results were obtained by using an exact rational LP solver,
in this case the program CDD written by Komei Fukuda \cite{cdd}. (Checking
emptiness of the polytope arising from the parameters $(p, q_2, q_2, q_3) = (11, 13, 17, 19)$
took us 14.5 hours on a laptop; for $(p, q_1, q_2, q_3) = (6, 7, 8, 9)$, the
computation takes around two minutes.) 
We note the negative result for $n =  46189$ does not disprove Conjecture \ref{conj}
for $n = 46189$ since our reduction from the certificate-finding problem
%Conjecture \ref{conj} 
to Problem \ref{theprob} is not if-and-only-if. 
%Checking Conjecture \ref{conj} ``manually'' for $n = 46189$ with the help of an exact rational LP solver seems like a reasonable next step, but the computation is daunting due to the large number of variables.

We will show that Problem \ref{theprob} has a solution when $2P > Q_1 + \cdots + Q_k$, which is equivalent to the condition $2/p > 1/q_1 + \cdots + 1/q_k$ when $P = n/p$ and $Q_j = n/q_j$. Theorem \ref{main} follows as a corollary. Our solution is a direct extension of the method Figs$.$ \ref{bfone}, \ref{bftwo} to higher dimensions. However, the existence of the analogues of the lines $L_1$, $L_2$, $L_3$ needs to be carefully proved in the $k$-dimensional case.

\begin{theorem}\label{finally}
Problem \ref{theprob} has a solution when $2P > Q_1 + \cdots + Q_k$.
\end{theorem}

\begin{proof}
Let $\ov{x} = [x_1-\frac{1}{2},x_1+\frac{1}{2}]\times \cdots \times [x_k-\frac{1}{2},x_k+\frac{1}{2}]$ for any $x = (x_1,\ldots,x_k) \in \zz^k$ (the ``cell around $x$'' or ``cell centered at $x$'') and let $\ov{\mS} = \bigcup_{x\in\mS}\ov{x}$ for any set $\mS \subseteq \zz^k$. Let $\I = \{x \in \zz^k: \langle x, z \rangle = h\}$, which may be empty. We will exhibit three parrallel hyperplanes $H_1$, $H_2$, $H_3$ in $\rr^k$ with $H_2$ equidistant to $H_1$ and $H_3$ such that, if $R^+$ is the region between $H_1$ and $H_2$ and $R^-$ is the region between $H_2$ and $H_3$,

	  {
	  \renewcommand{\theenumi}{\arabic{enumi}}
	  \renewcommand{\labelenumi}{(\theenumi)}
	  \begin{list}{2}{
	    \setlength{\itemindent}{23pt}
	    \setlength{\itemsep}{0pt}
	    \setlength{\parskip}{-100pt}
            \setlength{\leftmargin}{0pt}}
\vspace{0.5ex}
\item[(i)] $\vol(\ov{x} \cap R^+) > \vol(\ov{x} \cap R^-)$ for all $x \in \G^+$
\vspace{-0.5ex}
\item[(ii)] $\vol(\ov{x} \cap R^+) < \vol(\ov{x} \cap R^-)$ for all $x \in \G^-$
\vspace{-0.5ex}
\item[(iii)] $\vol(\ov{x} \cap R^+) = \vol(\ov{x} \cap R^-)$ for all $x \in \I$
\vspace{-0.5ex}
\item[(iv)] $\vol(\ov{x} \cap R^+) = 0, \vol(\ov{x} \cap R^-) = 0$ for all $x \notin \G^+ \cup \G^- \cup I$
           \end{list}
          }
\vspace{-1.2ex}
\noindent where `vol' is $k$-dimensional volume. If (i)--(iv) hold it is clear that the function $f(x) = \vol(\ov{x}\cap R^+) - \vol(\ov{x} \cap R^-)$ is periodic, zero-sum, and has the required sign and support (periodicity follows from the fact that $H_1$, $H_2$, $H_3$ are necessarily normal to $z$).

Let $\one = (1,\ldots,1) \in \zz^k$. Let $\alpha = \sup\{\langle y + \frac{1}{2}\one, z \rangle : y \in \zz^k, \langle y, z \rangle \leq h - P\}$, $\beta = \inf\{\langle y - \frac{1}{2}\one, z \rangle : y \in \zz^k, \langle y, z \rangle \geq h + P\}$. Since $z$ is rational there are some $ y_\alpha, y_\beta \in \zz^k$ such that $\alpha = \langle y_\alpha + \frac{1}{2}\one, z \rangle$, $\beta = \langle y_\beta - \frac{1}{2}\one, z\rangle$. Now $2P = (h+P) - (h-P) \leq \langle y_\beta, z \rangle - \langle y_\alpha, z \rangle = \langle y_\beta - \frac{1}{2}\one, z \rangle - \langle y_\alpha + \frac{1}{2}\one, z \rangle + \langle \one, z \rangle = \beta - \alpha + Q_1 + \cdots + Q_k < \beta - \alpha + 2P$ so $\beta - \alpha > 0$.

We distinguish between the two cases $\I = \emptyset$ and $\I \ne \emptyset$. Assume first that $\I \ne \emptyset$, so there exists an integer point $y_0$ such that $\langle y_0, x \rangle = h$. Then $\langle 2y_0 - y_\beta, z \rangle = 2h - \langle y_\beta, z \rangle \leq h - P$ and $2y_0 - y_\beta \in \zz^k$ so $\langle y_\alpha, z \rangle \geq  2h - \langle y_\beta, z \rangle$. Also $\langle 2y_0 - y_\alpha, z \rangle = 2h - \langle y_\alpha, z \rangle \geq h + P$ so $\langle y_\beta, z \rangle \leq 2h - \langle y_\alpha, z \rangle$. Therefore $h = \frac{1}{2}(\langle y_\beta, z \rangle + \langle y_\alpha, z \rangle) = \frac{1}{2}(\beta + \alpha)$.

Let $H_1 = \{x : \langle x, z \rangle = \alpha\}$, $H_2 = \{x : \langle x, z \rangle = h\}$, $H_3 = \{x : \langle x, z \rangle = \beta\}$. Then $R^+ = \{x : \alpha \leq \langle x, z \rangle \leq h\}$ and $R^- = \{x : h \leq \langle x, z \rangle \leq \beta\}$. The regions $R^-$, $R^+$ are nonempty since $\beta - \alpha > 0$ and $h = \frac{1}{2}(\alpha + \beta)$. If $x \in \G^+$ then $\vol(\ov{x} \cap \G^+) > 0$ since $\langle x + \frac{1}{2}\one, z\rangle = \langle y_\alpha + \frac{1}{2}\one, z \rangle + \langle x, z \rangle - \langle y_\alpha, z \rangle > \alpha$ (the last inequality follows because $\langle x, z \rangle > h - P$ and $\langle y_\alpha, z \rangle \leq h - P$) and since $\langle x - \frac{1}{2}\one, z \rangle < \langle x, z \rangle < h$. Moreover $\vol(\ov{x}\cap R^+) > \vol(\ov{x} \cap R^-)$ because $\langle x, z \rangle < h$, by convexity and central symmetry of the $k$-dimensional cube. Symmetrically, $\vol(\ov{x}\cap R^-) > \vol(\ov{x} \cap R^+)$ for all $x \in \G^-$, so conditions (i) and (ii) hold. Condition (iii) is obviously satisfied since $\I \subseteq H_2$. Finally if $x \notin \G^+ \cup \G^- \cup \I$ then $\langle x, z \rangle \leq h - P$ or $\langle x, z \rangle \geq h - P$; in the former case $\langle x + \frac{1}{2}\one \rangle \leq \alpha$ by definition of $\alpha$ so $\vol(\ov{x} \cap (R^+ \cup R^-)) = 0$, and in the latter case $\langle x - \frac{1}{2}\one, z \rangle \geq \beta$ by definition of $\beta$, so $\vol(\ov{x} \cap (R^+ \cup R^-)) = 0$, proving (iv).

Assume now that $\I = \emptyset$. 
Put $h' = (\beta + \alpha)/2$. Note $h' = (\langle y_\beta, z \rangle + \langle y_\alpha, z \rangle)/2$. 
We first show that if $y \in \G^+$ 
then $\langle y, z \rangle \leq h'$ and that if $y \in \G^-$ then $\langle y, z \rangle \geq h'$. Take any $y_0 \in \zz^k$ with $\langle y_0, z \rangle \leq h$. Let $y_1 = 2y_0 - y_\beta$. Then $y_1 \in \zz^k$ and $\langle y_1, z \rangle = 2\langle y_0, z \rangle - \langle y_\beta, z \rangle \leq h - P$ so $\langle y_1, z \rangle \leq \langle y_\alpha, z \rangle$. On the other hand $y_0 = (y_\beta + y_1)/2$ so $\langle y_0, z \rangle = (\langle y_\beta, z \rangle + \langle y_1, z \rangle)/2 \leq h'$ since $h' = (\langle y_\beta, z \rangle + \langle y_\alpha, z \rangle)/2$. Therefore $\langle y, z \rangle \leq h \implies \langle y, z \rangle \leq h'$ for all $y \in \zz^k$ and symmetrically $\langle y, z \rangle \geq h \implies \langle y, z \rangle \geq h'$ for all $y \in \zz^k$. In particular, $y \in \G^+ \implies \langle y, z \rangle \leq h'$ and $y \in \G^- \implies \langle y, z \rangle \geq h'$. 

If neither $\G^+$ or $\G^-$ have points on the hyperplane $\langle x, z \rangle = h'$ then we may proceed as in the first case after replacing $H_2$ with the hyperplane $\{x : \langle x, z \rangle = h'\}$, so we may assume that either $\G^+$ or $\G^-$---say $\G^+$---has points on the hyperplane $\langle x, z \rangle = h'$. Then $\langle x, z \rangle > h'$ for all $x \in \G^-$ since otherwise we would have $\langle y_a, z \rangle = \langle y_b, z \rangle$ for some $y_a \in \G^+$ and $y_b \in \G^-$, a contradiction. Moreover because $z$ is rational there exists some $\delta > 0$ such that $\langle x, z \rangle > h' + \delta$ for all $x \in \G^-$. 

Define $R^+_\evar = \{x \in \rr^k: \alpha + 2\evar \leq \langle x, z \rangle \leq h' + \evar\}$, $R^-_\evar = \{x \in \rr^k: h' + \evar \leq \langle x, z \rangle \leq \beta\}$ for any $\evar > 0$. Computing as above, we can see that $\vol(\ov{x}\cap R^+_0) > 0$ for all $x \in \G^+$ and $\vol(\ov{x}\cap R^-_0) > 0$ for all $x \in \G^-$, and that $\vol(\ov{x} \cap (R^+_0 \cup R^-_0)) = 0$ for all $x \notin \G^+ \cup \G^-$. Moreover because $z$ is rational there exists some $\gamma > 0$ such that $x \in \G^+ \implies \vol(\ov{x} \cap R^+_\evar) > 0$, $x \in \G^- \implies \vol(\ov{x} \cap R^-_\evar) > 0$ for all $\evar < \gamma$. Let $\ee > 0$ be smaller than $\delta$ and $\gamma$. Then $x \in \G^+ \implies \langle x, z \rangle \leq h' \implies \langle x, z \rangle < h' + \ee$ and $x \in \G^- \implies \langle x, z \rangle > h + \ee$ because $\ee < \delta$, so $\vol(\ov{x}\cap R^+_\ee) > \vol(\ov{x} \cap R^-_\ee)$ for all $x \in \G^+$ and $\vol(\ov{x}\cap R^+_\ee) < \vol(\ov{x} \cap R^-_\ee)$ for all $x \in \G^-$, fulfilling conditions (i) and (ii) with $R^+ = R^+_\ee$, $R^- = R^-_\ee$. Condition (iii) is trivially satisfied since $\I = \emptyset$ and condition (iv) is satisfied because $R^+_\ee \cup R^-_\ee \subseteq R^+_0 \cup R^-_0$.
\end{proof}

\begin{corollary}
Theorem \ref{main}.
\end{corollary}

\noindent
\textbf{Acknowledgements.} I thank Izabella Laba and
Phillip Rogaway for moral and financial support. I would also
like to thank the anonymous referee for his or her comments.

\begin{thebibliography}{99}
%\bibitem{bachman1} Gennady Bachman, On the coefficients of ternary cyclotomic polynomials, \emph{J. Number Theory} (2003), 104--116
%\bibitem{bachman2} Gennady Bachman, Ternary cyclotomic polynomials with an optimally large set of coefficients, \emph{Proc. Amer. Math. Soc.}, \textbf{132} no. 7 (2004), 1943--1950
%\bibitem{bateman} P.T. Bateman, C. Pomerance and R.C. Vaughan, On the size of the coefficients of the cyclotomic polynomial, Proc. Colloquium on Number Theory \textbf{34} (1981), Topics in Classical Number Theory, North Holland (1984), 171--202
%\bibitem{brent} R.P. Brent, On Computing Factors of Cyclotomic Polynomials, \emph{Math. Comput.} \textbf{61} (1993), 131--149
\bibitem{bruijn3} N.G. de Bruijn, On the factorization of cyclic groups, \emph{Indag. Math.}, \textbf{15} (1953), 370--377
\bibitem{conway} J.H. Conway and A.J. Jones, Trigonometric diophantine equations (On vanishing sums of roots of unity), \emph{Acta Arithmetica}, \textbf{30} (1976), 229--240
\bibitem{dcstein} D. Coppersmith and J.P. Steinberger, On the entry sum of cyclotomic arrays, \emph{INTEGERS: the Electronic Journal of Combinatorial and Additive Number Theory}, {\bf 6} (2006)
%\bibitem{coven1} Ethan M. Coven and Aaron Meyerowitz, Tiling the integers with translates of one finite set, \emph{J. Algebra} (1999), 161--174
%\bibitem{schmidt} V. Felsch and E. Schmidt, \"Uber Perioden in den Koeffizienten der Kreisteilungspolynome $F_{np}(x)$, \emph{Math. Z.}, \textbf{106} (1968), 267--272
\bibitem{cdd} K.~Fukuda, CDD. Available at \url{http://www.ifor.math.ethz.ch/~fukuda/cdd_home}.
%\bibitem{gralab} Andrew Granville, Izabella Laba, Yang Wang, On finite sets which tile the integers, preprint (2001)
%\bibitem{graver} J.E. Graver, On the foundation of linear and integer programming, \emph{Mathematical Programming} \textbf{9} (1975), 207--226
%\bibitem{hemmecke} R. Hemmecke, On the computation of atomic fibers, manuscript 2004
%\bibitem{hemmeckehilbert} R. Hemmecke, On the computation of hilbert bases and extreme rays of cones, arXiv.math: CO/0203105 v1, 12 March 2002
%\bibitem{hemmeckegraver} R. Hemmecke, On the positive sum property of and the computation of graver test sets, \emph{Mathematical Programming Ser. B}, \textbf{96} no. 2 (2003), 247--269
%\bibitem{justin} J. Justin, Bornes des coefficients du polyn\^ome cyclotomique et de certains autres polyn\^omes, C.R. Acad. Sci. Paris \textbf{268} (1969), S\'er. A, 995--997
%\bibitem{kolountzakis2} Mihail N. Kolountzakis, Translational Tilings of the Integers with Long Periods, \emph{Electronic Journal of Combinatorics}, \textbf{10} no. 1 (2003), R22.
%\bibitem{szalag} J.C. Lagarias, S. Szab\'o, Universal spectra and Tijdeman's conjecture on factorization of cyclic groups, \emph{J. Fourier Anal. Appl.} \textbf{7} no. 1 (2001), 63--70
\bibitem{lamleung} T.Y. Lam and K.H. Leung, On vanishing sums of roots of unity, \emph{J. Algebra}, \textbf{224} no. 1 (2000), 91--109
%\bibitem{lehmer} E. Lehmer, On the magnitude of the coefficients of the cyclotomic polynomial, \emph{Bull. Amer. Math. Soc.}, \textbf{42} (1936), 389--392
%\bibitem{lamleungbaby} T.Y. Lam and K.H. Leung, On the Cyclotomic Polynomial $\Phi_{pq}(X)$, Amer. Math. Monthly, \textbf{103} (1996), 562--564
%\bibitem{lenstra} H.W. Lenstra, Jr., Vanishing sums of roots of unity, Proc. Bicentennial Congress Wiskundig Genootschap (Vrije Univ. Amsterdam, 1978), Part II, pp. 249--268, Math. Centre Tracts 101, Amsterdam, 1979
%\bibitem{maclagan} Diane Maclagan, Antichains of monomial ideals are finite, \emph{Proc. Amer. Math. Soc.},  \textbf{129}  no. 6 (2001), 1609--1615
\bibitem{mann} Henry B. Mann, On linear relations between roots of unity, \emph{Mathematika}, \textbf{12} Part 2 no. 24 (1965), 107--117
%\bibitem{meng} Z. Meng, The distribution of the zeros of $L$-functions and the least prime in some arithmetic progression, \emph{Sci. China Ser. A} \textbf{43} no. 9 (2000), 937--944
%\bibitem{moller}  H. M\"oller, \"Uber die Koeffizienten des $n$-ten Kreisteilungspolynoms, \emph{Math. Z.}, \textbf{119} (1971), 33--40
%\bibitem{nagell} T. Nagell, ``Introduction to number theory'', New York: Wiley (1951), 158--160 and 164--168
\bibitem{bjorn} B. Poonen and M. Rubinstein, The number of intersection points made by the diagonals of a regular polygon, \emph{SIAM J. on Disc. Math.}, \textbf{11} no. 1 (1998), 133--156
%\bibitem{redei2} L. R\'edei, Ein Beitrag zum Problem der Faktorisation von endlichen Abelschen Gruppen, \emph{Acta Math. Acad. Sci. Hung.} \textbf{1} (1950), 197--204
\bibitem{redei3} L. R\'edei, \"Uber das Kresiteilungspolynom, \emph{Acta Math. Acad. Sci. Hungar.} \textbf{5} (1954), 27--28
%\bibitem{redei4} L. R\'edei, Nat\"urliche Basen des Kreisteilungsk\"orpers, Teil I, Abh. Math. Sem. Univ. Hamburg \textbf{23} (1959), 180--200
%\bibitem{ruzsa} I.D. Ruzsa, Appendix in ``R. Tijdeman, Periodicity and Almost-periodicity, preprint, August 2002''
\bibitem{schrijver} A. Schrijver ``Theory of Linear and Integer Programming'', Wiley-Interscience, 1986
%\bibitem{stein} S.K. Stein, S. Szab\'o ``Algebra and Tilings'', Mathematical Association of America Carus Mathematical Monograph series no. 25, 1994
%\bibitem{meisarray} J.P. Steinberger, Multiple tilings of $\zz$ by coordinate-sum projections of higher-dimensional arrays, submitted
%\bibitem{meisindecomposable} J.P. Steinberger, Indecomposable tilings of the integers with exponentially long periods, unsubmitted
\bibitem{meisminimal} J.P. Steinberger, Minimal vanishing sums of roots of unity with large coefficients, \emph{Proceedings of the London Mathematical Society}, \textbf{97} no. 3 (2008), 689--717.
\bibitem{schoenberg} I.J. Schoenberg, A note on the cyclotomic polynomial, \emph{Mathematika}, \textbf{11} (1964), 131--136
%\bibitem{tijdeman} R. Tijdeman, Decomposition of the integers as a direct sum of two subsets, Number Theory Paris 1992-1993
%\bibitem{eric} E. W. Weisstein, ``k-Tuple Conjecture'', from \emph{MathWorld}, http://mathworld.wolfram.com/k-TupleConjecture.html
%\bibitem{eric} E. W. Weisstein, ``Cyclotomic Polynomial'', from \emph{MathWorld}, http://mathworld.{-}wolfram.com/k-TupleConjecture.html
%\bibitem{vaughan1} R.C. Vaughan, Bounds for the coefficients of cyclotomic polynomials, \emph{Michigan Math. J.}, \textbf{21} (1975), 289--295
%\bibitem{vaughan2} R.C. Vaughan, Coefficients of cyclotomic polynomials and related topics, Proceedings of the Congress on Number Theory (Zarautz, 1984), Servicio Editorial de la Universidad del Pa\'is Vasco, 1990, 43--68 %Univ. Pa\'is Vasco-Euskal Herriko Unib., Bilbao, 1989
\end{thebibliography}
\end{document}
