Counting cycles and finite dimensional $L^p$ norms
Igor Rivin
We obtain sharp bounds for the number of $n$--cycles in a finite graph as a function of the number of edges, and prove that the complete graph is optimal in more ways than could be imagined. We prove sharp estimates on both $\sum_{i=1}^n x_{i}^k$ and $\sum_{i=1}^n |x_i|^k$, subject to the constraints that $\sum_{i=1}^n x_{i}^2 = C$ and $\sum_{i=1}^n x_i = 0.$
math0111106.tex
%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 


\documentclass[12pt]{amsart}

\usepackage{amsmath}
\usepackage{amsfonts, amssymb, amsthm}


\begin{document}

\title{Counting cycles and finite dimensional $L^p$ norms}
\copyrightinfo{1999}{Igor Rivin}
\author{Igor Rivin}

\address{Mathematics Department, University of Manchester and
  Mathematics Department, Temple University}
\curraddr{Fine Hall, Washington Rd, Princeton, NJ 08544}

\email{irivin@math.princeton.edu}

\thanks{I would like to thank {\'E}cole Polytechnique for its support, and Microsoft Research for its
hospitality.  I would also like to thank
  Ilan Vardi for mentioning the antisemitic question to me and
  carefully reading a previous version of this paper, and Omar Hijab, Laszlo Lovasz and
  Jacques Verstraete for interesting conversations.}

\date{\today}

\keywords{graphs, cycles, $L^p$ norms, graph spectra}

\subjclass{Primary 05C35, 05C12, 26D20}
\begin{abstract}
We obtain sharp bounds for the number of $n$--cycles in a finite graph
as a function of the number of edges, and prove that the complete
graph is optimal in more ways than could be imagined. We
prove sharp estimates on both $\sum_{i=1}^n x_{i}^k$ and $\sum_{i=1}^n
|x_i|^k$, subject to the constraints that $\sum_{i=1}^n x_{i}^2 = C$
and $\sum_{i=1}^n x_i = 0.$
\end{abstract}


\maketitle

\newtheorem{prop}{Proposition}
\newtheorem{defn}{Definition}
\newtheorem{lemma}{Lemma}
\newtheorem{thm}{Theorem}
\newtheorem{cor}{Corollary}
\newtheorem{remark}{Remark}
\newtheorem{ex}{Example}
\newtheorem{question}{Question}
\newtheorem{obs}{Observation}
\newcommand{\tr}{\mathrm{tr\:}}
\newcommand{\spec}{\mathrm{spec\:}}


\section*{Introduction}
This note was inspired by the following question, which had been
asked at the oral entrance exams, see \cite{vardi}, to the Moscow
State University Mathematics Department (MekhMat) to certain applicants:

\begin{question}\label{thequestion}
Let $G$ be a graph with $E$ edges. Let $T$ be the number of triangles
of $G$. Show that there exists a constant $C$, such that 
$T\leq C E^{3/2}$ for \textit{all} $G$. 
\end{question}

Before proceeding any further, let us answer the question. We will
assume that $G$ is a \textit{simple, loopless, undirected} graph --- that is,
there is exactly one edge connecting two vertices $v$ and $w$ of $G$,
and there are no edges whose two endpoints are actually the same
vertex.

We will need the following

\begin{defn}
The adjacency matrix $A(G)$ is the matrix with entries
$$(A(G)_{ij}) = \begin{cases}
  1, & \text{if $i$th and $j$th vertices of $G$ are
    adjacent}, \\
    0, & \text{otherwise.}
    \end{cases}
$$
\end{defn}

We shall also need the following observations:

\begin{obs} \label{obs1}
The number of paths of length $k$ between vertices $v_i$ and $v_j$ of
$G$ is equal to $A^k_{ij}$.
\end{obs}

The proof of this is immediate. It follows that the number of
\textit{closed} paths of length $k$ in $G$ is equal to the trace of
$A^k$. Of course, this statement has to be made with some care, since
the trace counts each closed path essentially $2 k$ times (the $2$ is
for the choice of orientation, the $k$ is for the possible starting
points, the ``essentially'' is because this is not true of paths which
consist of the same path repeated $l$ times; that's only counted $2
k/l$ times, or a path followed by retracing the steps backward --- such
a path is counted $k$ times, unless each half is a power of a shorter path,
in which case we count it $k/l$ times\ldots)


Unravelling the various cases, we have:

\begin{equation} \label{eq1}
\tr A = 0,
\end{equation}
since $G$ has no self-loops.
\begin{equation}\label{eq2}
\tr A^2 = 2 E(G),
\end{equation}
where $E(G)$ is the number of edges of $G$.
\begin{equation}\label{eq3}
\tr A^3 = 6 T(G),
\end{equation}
where $T(G)$ is the number of triangles of $G$, and
\begin{equation}\label{eqp}
\tr A^p = 2 p C_p(G),
\end{equation}
where $C_p(G)$ is the number of cycles of length $p$ of $G$ and $p$ is
a prime. For general $k:$
\begin{equation}\label{eqk}
\frac{\tr A^k}{2k} \leq \text{number of closed paths of length $k$ in
  $G$} \leq \frac{\tr A^k}{2}.
\end{equation}
A much more precise general statement can be made, but this will lead us too
far afield for the moment.

Since $A$ is symmetric, the following observation is self-evident:

\begin{obs}\label{obstr}
$$\tr A^k = \sum_{\lambda \in \spec A} \lambda^k,$$ where $\spec A$ is
the spectrum of $A$ --- the set of all eigenvalues of $A$.
\end{obs}

To answer Question \ref{thequestion} we will also need the following:

\begin{thm}\label{ineqthm}
Let ${\mathbf x}=(x_1, \dots, x_k, \dots)$ be a vector in some Hilbert
space $H$. Then for $p \ge 2$, 
\begin{equation}\label{holder}
\|{\mathbf x}\|_p \leq
  \|{\mathbf x}\|_2,
\end{equation}
where 
$$
\|\mathbf{x}\|_p = \left(\sum |x_i|^p\right)^{1/p},
$$ 
and
equality case in the inequality (\ref{holder}) occurs if and only if 
all but one of the $x_i$ are equal to $0$.
\end{thm}

\begin{proof}
It suffices to prove Theorem \ref{ineqthm} under the assumption that
$\|\mathbf x\|_2 = 1$ --- the general case follows by rescaling. This
case, however, is trivial, and follows from the observation that if
$0\leq y \leq 1$, then $\alpha < \beta$ implies that $y^\alpha \geq
y^\beta$, with equality if and only if $|y| \in \{0, 1\}.$
\end{proof}

\begin{cor}
Let $M$ be a symmetric matrix. Then
$$(\tr A^k)^2 \leq (\tr A^2)^k,$$ with equality if and only if all the
eigenvalues but one of $A$ are $0$.
\end{cor}

\begin{proof}[Proof of Corollary]
Since the eigenvalues of a symmetric matrix are real, and by
  Observation \ref{obstr}, $\tr A^l = \sum_{\lambda \in \spec 
  A} \lambda^l$, this follows immediately from Theorem \ref{ineqthm}.
 \end{proof}

Applying the Corollary in the case $k=3$, together with
eqs. (\ref{eq2}),(\ref{eq3}), we get:

\begin{equation}
(2 E)^{3/2} \geq 6 T,
\end{equation}
 and so
\begin{equation} \label{trestim}
T \leq \frac{2^{1/2}}{3} E^{3/2}.
\end{equation}
We have answered Question \ref{thequestion}, but we have done more: we
found an explicit value for the constant $C$ ($\sqrt{2}/3$), and the
method works without change to show that
\begin{equation}\label{pestim}
C_p \leq \frac{2^{p/2-1}}{p} E^{p/2},
\end{equation}
for prime $p$, while
\begin{equation}\label{kestim}
C_k \leq 2^{k/2-1} E^{k/2}
\end{equation}
in general.

\section{Sharper estimates for odd $n$}
Something not quite satisfying remains about the above argument (aside
from the weak bound for general $k$): it is clear that the equality
case in the estimates (\ref{trestim}) and (\ref{pestim}) is never
attained. This is so, because we know that the equality would
correspond to the spectrum of $A$ consisting of all $0$s and one
non-zero eigenvalue, but this contradicts eq. (\ref{eq1}). So,
potentially we could get a tighter bound by taking (\ref{eq1}) into
account. No easier said than done. We now have the following
optimization problem (for the number of triangles):

Maximize
$$\sum_{i=1}^n \lambda_i^3$$ subject to $$\sum_{i=1}^n \lambda_i = 0,$$
and $$\sum_{i=1}^n \lambda_i^2 = 2 E.$$

This is a typical constrained optimization problem, best approached
with Lagrange multipliers. To avoid (or increase) future confusion, we
note that by scale invariance the optimization problem is equivalent
to:

\medskip\noindent
Maximize
$$\sum_{i=1}^n x_i^3$$ subject to $$\sum_{i=1}^n x_i = 0,$$
and $$\sum_{i=1}^n x_i^2 = 1.$$

We know that to find the maximum we need to solve the following
gradient constraint:

$$\nabla(\sum_{i=1}^n x_i^3) = \lambda_1 \nabla(\sum_{i=1}^n x_i) +
\lambda_2 \nabla(\sum_{i=1}^n x_i^2).$$
In coordinates, we have a system of $n$ equations, with the $i$-th
being:
$$E_i:\qquad x_i^2 = \lambda_1 + \lambda_2 x_i.$$
This already tells us that whatever $\lambda_1$ and $\lambda_2$ may
be, there are only two possible values of $x_i$ (independently of
$i$) -- the two roots of the quadratic equation.

Summing all the equations, we get
$$1 = n \lambda_1,$$ so $\lambda_1 = 1/n$.
On the other hand, multiplying $E_i$ by $x_i$ and summing, we see
that:
\begin{equation}\label{lagsum}\sum_{i=1}^n x_i^3 = \lambda_2.
\end{equation}
The left hand side of eq. (\ref{lagsum}) is just the function we are
trying to maximize! It remains, thus, to find a good $\lambda_2.$

Rewriting the equation $E_i$ as
$$x_i^2 - \lambda_2 x_i - 1/n = 0,$$
we obtain:
\begin{equation}\label{quadform}
x_i = \frac{1}{2}\left[\lambda_2 \pm \sqrt{\lambda_2^2 +
    \frac{4}{n}}\right].
\end{equation}
Let us assume that the number of $i$ for which we take the plus sign
in the quadratic formula (\ref{quadform}) exceeds the number of $i$ for
which we take the minus sign by $k$. Summing all of the $x_i$ we get
$$
0 = \sum_{i=1}^n x_i = n \lambda_2 + k \sqrt{\lambda_2^2 +
  \frac{4}{n}}.
$$
(This implies already that $k < 0$.) This translates to the following
equation for $\lambda_2$:

$$\lambda_2^2 = \frac{4 k^2}{n(n^2 - k^2)}.$$ Since we want to make
$\lambda_2$ as large as possible (by eq. (\ref{lagsum})), we want to
make $k^2$ as large as possible on the right hand side. Since at least
one of the $x_i$ has to be negative and at least one positive, $-k$
cannot exceed $n-2$. Thus, the biggest possible value for $\lambda_2$
is
$$\lambda_2 = \frac{n-2}{\sqrt{n (n-1)}},$$
so, after all this work,  we have improved our estimate (\ref{trestim})
to
\begin{equation} \label{trestim2}
T \leq \frac{V-2}{\sqrt{V (V-1)}}\frac{2^{1/2}}{3} E^{3/2},
\end{equation}
($V$ being the number of vertices of our graph $G$).
This is somewhat disappointing: as $E$ (and thus $V$) goes to
infinity, the improvement disappears, and we have the same constant as
before. All the work has not been for nothing, however, for consider
the complete graph on $n$ vertices $K_n$. $E(K_n) = \frac{n (n-1)}{2},$
while $T(K_n) = \frac{n (n-1) (n-2)}{6},$ (since any pair of vertices
defines an edge, while any triple defines a triangle). A simple
computation shows that
\begin{equation}\label{compest}
T(K_n) =  \frac{n-2}{\sqrt{n (n-1)}}\frac{2^{1/2}}{3} E(K_n)^{3/2},
\end{equation}
so the inequality (\ref{trestim2}) is actually an equality in this
case. So the estimate (\ref{trestim2}) is sharp (since it
becomes an equality for an infinite family of graphs), and therefore
constant $\frac{2^{1/2}}{3}$ is also sharp.


A few remarks are in order (as usual).

Firstly, we have inadvertently computed the spectrum of the complete
graph.

The estimate (\ref{trestim2}) and the identity (\ref{compest})
together show that the complete graph $K_n$ is actually maximal
(in terms of the number of triangles) of all the graphs with the same
number of vertices and edges as it. This sounds wonderful, until
we realize that it is the \textit{only} graph with $n$ vertices
and $n (n-1)/2$ edges. The identity (\ref{compest}) together with
(\ref{trestim2}) do seem to \textit{suggest} that the complete graph
is maximal (for the number of triangles) of all the graphs with
the same number of edges. We state this as

\begin{question}
Show that the complete graph $K_n$ is the graph containing the most
triangles of the graphs with $\frac{(n-1) n}{2}$ edges.
\end{question}

This question turns out to be not too difficult. The answer is the
content of the following

\begin{thm}\label{compopt}
In a graph $G$ with no more than $n(n-1)/2$ edges, each edge
is contained, on the average, in no more than $n-2$ triangles.
Equality holds only for the complete graph $K_n$.
\end{thm}

\begin{proof}
We will prove the theorem by  induction. Let $v$ be a vertex in
$G$ of maximal degree $d$. Such a vertex is contained in, at most,
$T_v=\min(d(d-1)/2, E(G)-d)$ triangles. This is because there is
at most one triangle per edge connecting two vertices adjacent to
$v,$ and removing $v$ together with the edges incident to it
leaves a graph $G^\prime$ with $T(G)-T_v$ triangles, $E(G)-d$
edges, and $V(G)-1$ vertices.

Note, first of all, that if the two endpoints of an edge $e$ in $G$
have valences $d_1$ and $d_2$, then, if $m = \min(d_1, d_2)$, $e$
is contained in at most $m-1$ triangles. So if the degree of $v$
(assumed to be maximal) was smaller than $n-1$, \textit{no} edge
of $G$ was contained in as many as $n-2$ triangles, so we are
done.

If $d > n-1$, then $G^\prime$ has $n(n-1)/2 -d$ edges, and so each
edge incident to $v$ is contained, on the average, in at most
$\left[n(n-1)-2d\right]/d$ triangles. Now, $$n(n-1)-2d -d(n-2) =
n(n-1) - dn = n(n-1-d) < 0,$$ so the edges incident to $d$ are
contained, on the average, in fewer than $n-2$ triangles. The
number of edges of $G^\prime$ is smaller than $(n-1)(n-2)/2$ (by a
simple calculation), so each of them is contained, on the average,
in at most $n-3$ triangles. Since, at best, each of them was
contained in one more triangle containing $v$, this tells us that
the average was smaller than $n-2$.

If $d=n-1$, repeating the argument as above shows us that for the
 equality to hold $G^\prime$ has to be a complete graph on
$n-1$ vertices, and so $G$ is a complete graph on $n$ vertices.
\end{proof}

Since most numbers are not triangular (triangular numbers being those
of the form $n (n-1)/2$), one can naturally ask the following

\begin{question} Is there a simple characterization of graphs with $k$
  edges which are ``triangle maximal'' (for all $k$)?
\end{question}

and

\begin{question}
Consider all graphs with $E$ edges and $V$ vertices. Is there a way to
characterize the one with the most triangles.
\end{question}

\section{Estimates on power sums}
Moving away from graphs as such, the reader will have noted,
perhaps, that our way to maximize the $\sum_{i=1}^n x_i^p$ subject
to the constraints $\|\mathbf x\| = 1$ and $\sum_{i=1}^n x_i = 0$
doesn't work so well for $p \neq 3$, which brings up the
questions:

\begin{question}
Which point $\mathbf{x}$ on the unit sphere $\mathbb{S}^{n-1} \in
\mathbb{R}^n$ and satisfying $\sum_{i=1}^n x_i = 0$ has the
biggest $\sum_{i=1}^n x_i^p$? Which has the biggest $L^p$ norm
(this question is the same of even integer $p$, but quite
different for odd $p$. For non-integer $p$, the first question
doesn't make that much sense...
\end{question}

\section{Odd $p$}
It turns out that it is easiest to  minimize the sum of $p$-th 
powers for $p$ odd. The maximum in this case is attained a the 
point satisfying the constraints of largest $L^\infty$ norm. For 
arbitrary $p$, the argument is a little more subtle -- see the 
proof of Theorem \ref{lovasz}. 
\begin{thm}\label{oddthm}
The maximal value of $\sum_{i=1}^n x_i^{2p+1}$ subject to the
constraints $\sum_{i=1}^n x_i^2 = 1,$ and $\sum_{i=1}^n x_i = 0$
is attained at the point where $$x_1 = \sqrt{\frac{n-1}{n}}$$ and
$$x_j = -\sqrt{\frac{1}{(n-1)n}} \qquad  j=2,\dots, n.$$ The value
of this maximum is
$M_{n, {2p+1}}$, where
$$M_{n, k}=\frac{(n-1)^{k-1}-1}{n^{k/2}(n-1)^{k/2-1}}.$$
\end{thm}

\begin{proof}
As before, we set up the Lagrange multiplier problem, which has
$n$ equations of the form:
\begin{equation}\label{geneq}
E_i:\qquad x_i^{2p} = \lambda_1 + \lambda_2 x_i.
\end{equation}
Adding all of the equations together, we find that
\begin{equation}\label{l1eq}
n\lambda_1 = \sum_{i=1}^n x_i^{2p},
\end{equation}
while multiplying $E_i$ by $x_i$ and adding the results together
we get
\begin{equation}\label{l2eq}
\lambda_2 = \sum_{i=1}^n x_i^{2p+1},
\end{equation}
so that that sought-after sum is equal to $\lambda_2$, as before.

Further, note that the derivative of $x^{2p}-\lambda_2 x -
\lambda_1$ is equal to $(2p-1) x^{2p-1} - \lambda_2$, which has
exactly $1$ real zero (whatever the value of $\lambda_2$.
Therefore, the equation $x^{2p}-\lambda_2 x - \lambda_1 = 0$ has
at most two real roots. The specifics of our problem are such that
we know that there are exactly two roots, one positive, the other
negative. Call the positive root $\alpha_1$, and the negative root
$\alpha_2$, and suppose that $n_1$ of the $x_i$ are equal to
$\alpha_1$, while $n_2 = n - n_1$ of the $x_i$ are equal to
$\alpha_2$. It follows that
 \begin{equation}\label{aeq}
 \alpha_1 = -
\frac{n_2}{n_1} \alpha_2.
\end{equation}

By eq. (\ref{l1eq}) and (\ref{l2eq}) it follows that $$\lambda_1 =
\frac{1}{n}\left(n_1 \alpha_1^{2p} + n_2
\alpha_2^{2p}\right),\qquad \lambda_2 = n_1 \alpha_1^{2p+1} + n_2
\alpha_2^{2p+1}.$$

 From eq. (\ref{geneq}), we have the following equation for
$\alpha_2$ (where we have substituted for $\alpha_2$ from the
equation (\ref{aeq}):

\begin{equation}
\alpha_2^{2p} = \frac{1}{n}\left(n_1\left(-\frac{n_1}{n_2}
\alpha_2\right)^{2p} + n_2 \alpha_2^{2p}\right)+\left(n_1
\left(-\frac{n_1}{n_2} \alpha_2\right)^{2p+1} + n_2
\alpha_2^{2p+1}\right)\alpha_2.
\end{equation}
Dividing through by $\alpha_2^{2p}$ get

$$1 = \frac{1}{n}\left[\frac{n_2^{2p}}{n_1^{2p-1}} + n_2\right] +
\alpha_2^2\left[-\frac{n_2^{2p+1}}{n_1^{2p}} + n_2\right],$$
 from where, rearranging terms, and replacing $n$ by
$n_1+n_2$, we get

\begin{equation*}
 \alpha_2^2 =
\frac{\frac{1}{n_2} - \frac{1}{n_1+n_2}
\left[\left(\frac{n_2}{n_1}\right)^{2p-1}+1\right]}
{1-\left(\frac{n_2}{n_1}\right)^{2p}} = \frac{n_1}{n_2 (n_1+n_2)},
\end{equation*}
 since, amazingly, everything cancels after clearing
denominators.

So, finally, we see that $$\alpha_2^2 = \frac{n_1}{n_2(n_1+n_2)}$$
while $$\alpha_1^2 = \frac{n_2}{n_1 (n_1+n+2)},$$ thus showing the
first part of the theorem.

 Now, the sum $S$ which we seek is given by
$$S=n_1 \alpha_1 + n_2 \alpha_2 =
\frac{1}{n^{p+1/2}}\left[\frac{n_2^{p+1/2}}{n_1^{p-1/2}} -
\frac{n_1^{p+1/2}}{n_2^{p-1/2}}\right].$$ This is obviously
maximal when $n_2$ is as large as possible, to wit $n-1$, from
which the second part of the theorem follows immediately.
\end{proof}


Notice that since the values of $x_i$ are independent of $p$, it 
follows from Theorem \ref{oddthm} that we have proved the 
following
\begin{thm}
Let $p$ be an odd prime. A graph $G$ with $V$ vertices and $E$ edges has
at most
$$
C_{V,E} = 
\frac{(V-1)^{p-1}-1}{V^{(p+1)/2}(V-1)^{(p-1)/2-1}}\frac{2^{p/2-1}}{p} 
E^{p/2}
$$
$p$-cycles, where equality holds if and only if $G$ is the complete
graph $K_{|V|}.$
\end{thm}

\section{General $p$}
The remainder of the paper will be devoted to the proof of the
following Theorem:
\begin{thm}
\label{mainthm} Let $p>2.$
Then the maximum of 
the sum 
\begin{equation*}S_{n, p} = \sum_{i=1}^n x^p,
\end{equation*} subject to the constraints
$$\sum_{i=1}^n x_i = 0,$$ and 
$$\sum_{i=1}^n x_i^2 = 1$$ is assumed at the point
$x_1 = (1-1/n)^{1/2}, x_2 = \dots = x_n = 
\left[n(n-1)\right]^{-1/2}.$ The maximal value of $S_{n, p}$ then 
equals $S^*_{n, p} = =\frac{(n-1)^{k-1}+1}{n^{k/2}(n-1)^{k/2-1}}.$
\end{thm}

Theorem \ref{mainthm} was already shown above in the case where $p$
was odd. The proof for even $p$ will proceed as follows. First, we
show Theorem \ref{lovasz}, which deals with all but a finite number of
exceptions. Then, in sections \ref{symmetric} and \ref{k4} we will
deal with the exceptions. It should be noted that that the proof of
Theorem \ref{lovasz} does not rely on the integrality of $p$ in any
essential way, and can be viewed as a result on general $L^p$ norms on
finite-dimensional vector spaces. The proof leaves a a white spot for
small dimensions and degree $p$, but it should be noted that sections
\ref{symmetric} and \ref{k4} are devoted only to the integer version
of the theorem as stated above, and so our result for arbitrary $L^p$
norms is not quite complete.

\begin{thm}
\label{lovasz} Let $p>2$, $p$ even, and such that the pair $(n, 
p)$ is not in the set $$E=\{(3, 4), (4, 4), (5, 4), (6,4), (7,4), 
(3, 6), (4, 6), (3, 8), (3, 10), (3, 12)\}.$$ Then the maximum of 
the sum 
\begin{equation*}S_{n, p} = \sum_{i=1}^n x^p,
\end{equation*} subject to the constraints
$$\sum_{i=1}^n x_i = 0,$$ and 
$$\sum_{i=1}^n x_i^2 = 1$$ is assumed at the point
$x_1 = (1-1/n)^{1/2}, x_2 = \dots = x_n = 
\left[n(n-1)\right]^{-1/2}.$ The maximal value of $S_{n, p}$ then 
equals $S^*_{n, p} = =\frac{(n-1)^{k-1}+1}{n^{k/2}(n-1)^{k/2-1}}.$
\end{thm}

First, we need a lemma.
\begin{lemma}
\label{llemma}
Let $x_1 \geq x_2 \geq \dots x_n$ be a maximizer for our optimization problem. Then
$x_1^{p-2} \geq M_{n, p},$ where $M_{n, k}$ is defined in the statement of Theorem
\ref{oddthm}.
\end{lemma}

\begin{proof}
$$
M_{n,p} \leq S^*_{n, p}=\sum_{i=1}^n x_i^{p} = \sum_{i=1}^n 
x_i^{p-2} x_i^2 \leq x_1^{p-2} \sum_{i=1}^n x_i^2 = x_1^{p-2},
$$
where the first equality uses the fact that $(x_1, \dots, x_p)$ is a maximizer.
\end{proof}

\medskip\noindent
\textbf{Notation.} We will denote $M_{n, p}^{1/(p-2)}$ by $N_{n, 
p}.$

\begin{cor}
\label{upperbd}
 Let $x_1 \geq x_2 \geq \dots x_n$ be a maximizer 
for the optimization problem. Then 
$$x_2^2 \leq 1-N^2_{n, p}.$$
\end{cor}

\begin{proof}
Immediate from the constraints.
\end{proof}

\begin{proof}[Proof of Theorem \ref{lovasz}]
Setting up the Lagrange multiplier problem as before, we see that 
\begin{equation}
\label{lageq} x_i^{p-1}  = \lambda_1 + \lambda_2 x_i
\end{equation}
must hold at the maximum.
 As in the 
proof for odd $p$, if we let $f_p(x) = x^{p-1} - \lambda_1 - 
\lambda_2 x$, we note that $f^\prime_p(x) = (p-1) x^{p-2} - 
\lambda_2.$ Since $f^\prime_p(x)$ has exactly two real zeros: 
$z_{\pm} =  \pm(\lambda_2/(p-1))^{1/(p-2)}$ -- we will write $z = 
|z_\pm|.$ $f_p(x)$ has at most $3$ real zeros $t_1 \leq t_2 \leq 
t_3$, where $t_1 \leq z_-$ and $t_3 \geq z_+.$ If we succeed in 
showing that $z 
> \sqrt{1-N^2_{n, p}}$, then it will follow that there are at most two 
distinct values of $x_i$, and the argument for odd $p$ will lead 
us to the desired conclusion. To do that, we note that by 
multiplying equations (\ref{lageq}) by $x_i$ and adding them over 
$i$, we see that $\lambda_2 = S^*_{n, p} \geq M_{n, p},$ and 
therefore
$$z \geq (M_{n, p}/(p-1))^{1/(p-2)}.$$ Thus, our conclusion will 
follow if we show that 
$$\left(\frac{M_{n, p}}{p-1}\right)^{\frac{2}{p-2}} \geq 1-N^2_{n, p} = 1 - M^{\frac{2}{p-2}}_{n, p},$$
or equivalently:
$$M^{\frac{2}{p-2}}_{n, p} \geq \frac{1}{1+(p-1)^{-\frac{2}{p-2}}}.$$
Since it is clear that $$M_{n, p} \geq 
\left(\frac{n-1}{n}\right)^{\frac{p}{2}},$$ it would suffice to 
show that 
\begin{equation} \label{fundineq} 1-\frac{1}{n} \geq 
\frac{1}{\left(1+(p-1)^{-\frac{2}{p-2}}\right)^{\frac{p-2}{p}}}. 
\end{equation} 
Let us denote the right hand side in the desired inequality 
(\ref{fundineq}) by $g(p).$
\begin{lemma}
\label{plemma} The function $g(p)$ is monotonically decreasing 
for $p > 2$, and $\lim_{p \rightarrow \infty} = 1/2.$
\end{lemma}
\begin{proof}[Proof of Lemma \ref{plemma}]
Note that $g(p) = 1/h(p),$ where 
$$h(p) = \left(1+(p-1)^{-\frac{2}{p-2}}\right)^{\frac{p-2}{p}}.$$
The fact that $\lim_{p \rightarrow \infty} h(p) = 2$ is obvious. 
Since $\frac{p-2}{p}$ is an increasing function of $p,$ it is 
enough to show that $k(p)=(p-1)^{-\frac{2}{p-2}}$ is an 
increasing function of $p.$ Write 
$$
l(p) = \log k(p) = - \frac{2}{p-2} \log (p-1).
$$
Now \begin{eqnarray*}\frac{d l}{d p} &= -\frac{2}{(p-2)(p-1)} + 
\frac{2}{(p-2)^2}\log(p-1)\\ &= \frac{2}{p-2} 
\left(-\frac{1}{p-1} + \frac{\log(p-1)}{p-2}\right). 
\end{eqnarray*}
 Since $\log (p-1) > \frac{p-2}{p-1},$ it follows 
that $\frac{dl}{dp} > 0$ whenever $p > 2$, and the assertion of 
the lemma follows.
\end{proof}
The proof of the theorem now follows easily: by Lemma 
\ref{plemma}, the statement of the theorem is true for any pair 
$(n, p)$ such that $n > n(p)$, where $1-1/n(p) \geq g(p),$ and 
$n(p)$ is chosen to be minimal with that property. The explicit 
form of the exceptional set follows by a simple machine 
computation.  
\end{proof}

\section{Power sums and symmetric functions and some  optima.}
\label{symmetric}
\subsection{A brief introduction to symmetric functions.}
Let us first introduce the \textit{elementary symmetric functions
  $e_k(x_1, \dots, x_n)$}. These are defined simply as 
$$e_k(x_1, \dots, x_n) = \mbox{$(-1)^k$ coefficient of $x^{n-k}$ in $(x
  - x_1) \cdots (x - x_n),$}$$ while $e_k(x_1, \dots, x_n) = 0$ for $k
> n.$
The \textit{symmetric function theorem} (see, eg, \cite{lang}) tells
us that any symmetric polynomial  of $x_1, \dots, x_n$ can be written
as a polynomial in $e_1(x_1, \dots, x_n), \dots e_n(x_1, \dots, x_n).$
Recall that a polynomial $f$ is \textit{symmetric} if 
$f(x_1, \dots, x_n) = f(x_{\sigma(1)}, \dots, x_{\sigma(n)}),$ where
$\sigma$ is an arbitrary permutation of $n$ letters.
An example of a symmetric polynomial is the \textit{$k$-th power sum} 
$t_k(x_1, \dots, x_n) = x_1^k + \cdots + x_n^k.$ In this case, the
algorithm to express $t_k$ in terms of $e_k$ was found by Isaac
Newton, and can be summarized as follows:

\begin{itemize}

\item{(a)} When $n > k$, then 
\begin{equation}t_k(x_1, \dots, x_{n-1}) =
  f(e_1(x_1, \dots, x_{n-1}), \dots, e_n(x_1, \dots, x_{n-1})
\end{equation}
 implies
  that 
\begin{equation}
\label{reca}
t_k(x_1, \dots, x_n) =   f(e_1(x_1, \dots, x_{n}), \dots,
  e_n(x_1, \dots, x_{n}).
\end{equation}

\item{(b)} When $n \leq k$, then 
\begin{equation}
\label{recb}
t_k(x_1, \dots, x_n) +  \sum_{i=1}^n (-1)^i e_i(x_1, \dots, x_n)
t_{k-i}(x_1, \dots, x_n).
\end{equation}
\end{itemize}

Both parts (a) and (b) are easily shown: part (a) by noting that the
difference between the right and the left hand sides of
Eq. (\ref{reca}) vanishes when $x_n = 0$, and so, by symmetry, that
difference must be divisible by $x_1 \cdots x_n$, and hence is
identically $0$ (since the degree is smaller than $n$); part (b) by
considering a matrix $A$ with eigenvalues $x_1, \dots, x_n$, remarking
that $A$ satisfies its characteristic polynomial, then taking traces.

\subsection{$n=3$} First, note that our constraints that $t_1(x_1,
\dots, x_n) = 0$ and $t_2(x_1, \dots, x_n) = 1$ imply that 
$e_1(x_1, \dots, x_n) = t_1(x_1, \dots, x_n) = 0,$ while, since
$t_1^2 - 2 e_2 = t_2,$ it follows that $e_2(x_1, \dots, x_n) =
-\frac{1}{2}.$ 

Specializing to $n=3$, we see from Eq. (\ref{recb}) that
$$t_k(x_1, x_2, x_3) = \frac{1}{2} t_{k-2}(x_1, x_2, x_3) +
t_{k-3}(x_1, x_2, x_3) e_3(x_1, x_2, x_3),$$
which implies firstly that $t_4(x_1, x_2, x_3) = \frac{1}{2}$ and
secondly that $t_k(x_1, x_2, x_3)$ is a polynomial in $e_3(x_1, x_2,
x_3)$ \textit{with positive coefficients}. This means that the maximum
of $t_k(x_1, x_2, x_3)$ is achieved for those values of $x_1, x_2,
x_3$ which maximize the value of $x_1 x_2 x_3$ (subject to our
constraints). But since we know that for $k$ large (or $k$ odd) that
happens at $x_1 = \sqrt{2/3}, x_2 = x_3 = - \sqrt{1/6},$ this finishes
the proof of $(n=3).$

\subsection{$n=4$}
A routine computation using equations (\ref{reca}, \ref{recb}) leads
to the following:
\begin{gather}
\label{eqg1}
t_3(x_1, x_2, x_3, x_4) = 3 e_3(x_1, x_2, x_3, x_4),\\
\label{eqg2}
t_4(x_1, x_2, x_3, x_4) = \frac{1}{2} - 4 e_4(x_1, x_2, x_3, x_4),\\
\label{eqg3}
t_6(x_1, x_2, x_3, x_4) = \frac{1}{4} + 3 e_3^2(x_1, x_2, x_3, x_4) -
3 e_4(x_1, x_2, x_3, x_4).
\end{gather}
Since we know that $t_3(x_1, x_2, x_3, x_4)$ is maximized at the point
$x_1 = \sqrt{3/4}, x_2 = x_3 = x_4 = \sqrt{1/12},$ we know that
$e_3(x_1, x_2, x_3, x_4)$ is maximized at that point, and thus, to
finish the case $n=4$ we need to show that $t_4(x_1, x_2, x_3, x_4)$
is \textit{minimized} at that same point. In general, to  minimize
$e_n(x_1, \dots, x_n)$ subject to $t_1(x_1, \dots, x_n) = 0$ and
$t_2(x_1, \dots, x_n) = 1$ we set up the usual Lagrange multiplier
problem, and have the Lagrange equations for the critical points:
$$\frac{e_n(x_1, \dots, x_n)}{x_i} = \lambda_1 + \lambda_2 x_i,$$
or
$$e_n(x_1, \dots, x_n) = \lambda_1 x_i  + \lambda_2 x_i^2.$$
Since the right hand side is a quadratic, it follows immediately that
there are exactly two different values of the coordinates, and the
rest of the argument (at least when $n=4$) is routine and shows that
$e_4(x_1, \dots, x_4)$ is minimized exactly when $e_3(x_1, \dots,
x_4)$ is maximized, which does it for $t_4(x_1, x_2, x_3, x_4)$ and
$t_6(x_1, x_2, x_3, x_4).$

\section{$p=4$}
\label{k4}
In this section we eliminate the exceptional cases of the form $(n,
4),$ for all $n.$ Consider, then, the vector $(x_1, \dots, x_n)$ such
that $\sum_{i=1}^n x_i = 0,$ $\sum_{i=1}^n x_i^2 = 1$ and
$\sum_{i=1}^n x_i^4$ is maximal. Such a vector must satisfy the
lagrange multiplier equations:
\begin{equation}
\label{lag4}
x_i^3 = \lambda x_i + \mu.
\end{equation}
If there are only two different values of the coordinates, then we are
done. It is easy to see directly that there are at most \emph{three}
distinct values, as follows: suppose $x_1 \neq x_j.$ then, subtracting
the Lagrange equation (\ref{lag4}) for $x_1$ from that of $x_j,$ we
obtain:
\begin{equation*}
x_1^3 - x_j^3 = \lambda(x_1 - x_j).
\end{equation*}
Dividing through by $x_1 - x_j$ we get
\begin{equation}
\label{quadlag}
x_j^2 + x_j x_1 + x_1^2 - \lambda = 0.
\end{equation}
This is a quadratic equation for $x_j$, and we see that $x_j$ could be
either one of the two roots. So, if there are more than two distinct
values of the coordinates, there are exactly three, call them $\alpha
= x_1, \beta, \gamma.$ Since $\beta, \gamma$ are the two roots of the
quadratic equation (\ref{quadlag}), we see that 
\begin{equation}
\label{linrel}
\beta + \gamma = -\alpha.
\end{equation}
Let us assume that $\alpha = \max (\alpha, \beta, \gamma).$
Furthermore, let us assume that $n \geq 4$ (since the case $n=3$ was
dealt with above). That being the case, it is clear that
\begin{equation}
\label{quadineq}
1=\sum_{i=1}^n x_i^2 \geq \alpha^2 + 2\beta^2 + \gamma^2.
\end{equation}
Let $\alpha$ be fixed. Then, the minimum of $2\beta^2 + \gamma^2$
subject to the relation (\ref{linrel}) is achieved for $\beta =
-(\frac{2}{3}\alpha),$ and $\gamma = -\frac{1}{3} \alpha$ (this is
easily shown using Lagrange multipliers), and so 
$$\alpha^2 + 2\beta^2
+ \gamma^2 \geq \alpha^2 (1+2\frac{4}{9} + \frac{1}{9} = 2 \alpha^2.$$
This, together with the inequality (\ref{quadineq}), implies that 
$$\alpha^2 \leq \frac{1}{2}.$$ 
On the other hand, Lemma \ref{llemma} tells us that 
$$\alpha^2 \geq \left(\frac{n-1}{n}\right)^2,$$ if our vector is a
maximizer.
The last two inequalities imply that 
$$\left(\frac{n-1}{n}\right)^2 \leq\frac{1}{2},$$
which is only satisfied for $n=1, 2, 3.$ The argument is now
complete. \qed

\subsection*{Notes on the bibliography} It is hoped that this paper is
reasonably self-contained, however, I would be remiss not to give some
references to related literature. The literature on graph eigenvalues
is vast. For some entry points, the reader is advised to look at the
books of Biggs (\cite{biggs}) and Cvetkovic-Doob-Sachs (\cite{cvet}) for a
general introduction to graph theory, Bollobas' book \cite{bollo} is
good, among many other.

\bibliographystyle{amsplain}
\begin{thebibliography}{999999999999}

\bibitem{biggs}
N.~Biggs.
\textit{Algebraic Graph Theory}, Second Edition, Cambridge
Mathematical Library, Cambridge University Press, Cambridge 1993.

\bibitem{bollo}
B.~Bollobas.
\textit{Modern graph theory}, GTM 184, Springer-Verlag, New York,
1998.

\bibitem{cvet}
D.~Cvetkovic, M.~Doob, H.~Sachs.
\textit{Spectra of Graphs, Theory and Applications}, Third Edition,
Johann Ambrosius Barth, Heidelberg, 1995.

\bibitem{lang}
S.~Lang.
\textit{Algebra,} Second Edition, Addison-Wesley Publishing Co., 1984

\bibitem{vardi}
I.~Vardi.
\textit{Mekh-mat entrance examination questions}, IHES preprint, 1999.
\end{thebibliography}
\end{document}

math0111106.extracted_bib
\begin{thebibliography}{999999999999}

\bibitem{biggs}
N.~Biggs.
\textit{Algebraic Graph Theory}, Second Edition, Cambridge
Mathematical Library, Cambridge University Press, Cambridge 1993.

\bibitem{bollo}
B.~Bollobas.
\textit{Modern graph theory}, GTM 184, Springer-Verlag, New York,
1998.

\bibitem{cvet}
D.~Cvetkovic, M.~Doob, H.~Sachs.
\textit{Spectra of Graphs, Theory and Applications}, Third Edition,
Johann Ambrosius Barth, Heidelberg, 1995.

\bibitem{lang}
S.~Lang.
\textit{Algebra,} Second Edition, Addison-Wesley Publishing Co., 1984

\bibitem{vardi}
I.~Vardi.
\textit{Mekh-mat entrance examination questions}, IHES preprint, 1999.
\end{thebibliography}