TITLE: Historical question in analytic number theory
QUESTION [14 upvotes]: The analytic continuation and functional equation for the Riemann zeta function were proved in Riemann's 1859 memoir "On the number of primes less than a given magnitude." What is the earliest reference for the analytic continuation and functional equation of Dirichlet L-functions?  Who first proposed that they might satisfy a Riemann hypothesis?  Dirichlet did none of these things; his paper dates from 1837, and as far as I know he only considered his L-functions as functions of a real variable.

REPLY [25 votes]: To extend on Matt's comment about Euler, here is something I wrote up some years ago about Euler's discovery of the functional equation only at integral points. I hope there are no typos.
Although Euler never found a convergent analytic expression for
$\zeta(s)$ at negative numbers, in 1749 he published a method of
computing
values of the zeta function at negative integers by a precursor of
Abel's Theorem applied to a divergent series.  The
computation led him to the asymmetric functional equation of
$\zeta(s)$.
The technique uses the function
$$
\zeta_{2}(s) = \sum_{n \geq 1} \frac{(-1)^{n-1}}{n^s} =
1 - \frac{1}{2^s} + \frac{1}{3^s} - \frac{1}{4^s} + \dots.
$$
This looks not too different from $\zeta(s)$, but has the advantage
as an alternating series of
converging for all positive $s$.  For $s > 1$,
$\zeta_2(s) = (1 - 2^{1-s})\zeta(s)$.
Of course this is true for complex $s$, but
Euler only worked with real $s$, so we shall as well.
Disregarding convergence issues, Euler wrote
$$
\zeta_{2}(-m) = \sum_{n \geq 1} (-1)^{n-1}n^m = 1 - 2^m + 3^m - 4^m +
\dots,
$$
which he proceeded to evaluate as follows.  Differentiate
the equation
$$
\sum_{n \geq 0} X^n = \frac{1}{1-X}
$$
to get
$$
\sum_{n \geq 1} nX^{n-1} = \frac{1}{(1-X)^2}.
$$
Setting $X = -1$,
$$
\zeta_{2}(-1) = \frac{1}{4}.
$$
Since $\zeta_{2}(-1) = (1-2^2)\zeta(-1)$, $\zeta(-1) = -1/12$.  Notice we can't set $X = 1$ in the second power series and compute $\sum n = \zeta(-1)$ directly.  So $\zeta_2(s)$ is nicer than $\zeta(s)$ in this Eulerian way.
Multiplying the second power series by $X$ and then differentiating, we get
$$
\sum_{n \geq 1} n^2X^{n-1} = \frac{1+X}{(1-X)^3}.
$$
Setting $X = -1$,
$$
\zeta_{2}(-2) = 0.
$$
By more successive multiplications by $X$ and differentiations, we get
$$
\sum_{n \geq 1} n^3X^{n-1}  = \frac{X^2+4X+1}{(1-X)^4},
$$
and
$$
\sum_{n \geq 1} n^4X^{n-1} = \frac{(X+1)(X^2+10X+1)}{(1-X)^5}.
$$
Setting $X = -1$, we find $\zeta_{2}(-3) = -1/8$ and
$\zeta_{2}(-4) = 0$.  Continuing further, with the recursion
$$
\frac{d}{dx} \frac{P(x)}{(1-x)^n} = \frac{(1-x)P'(x) + nP(x)}{(1-x)^{n+1}},
$$
we get
$$
\sum_{n \geq 1} n^5X^{n-1}  =  \frac{X^4+26X^3+66X^2 + 26X +1}{(1-X)^6},
$$
$$
\sum_{n \geq 1} n^6X^{n-1} =  \frac{(X+1)(X^4 + 56X^3 + 246X^2 + 56X+1)}
{(1-X)^7},
$$
$$
\sum_{n \geq 1} n^7X^{n-1} =  \frac{X^6 + 120X^5 + 1191X^4 + 2416X^3 +
1191X^2 + 120X + 1}{(1-X)^8}.
$$
Setting $X = -1$, we get $\zeta_{2}(-5) =
1/4, \ \zeta_{2}(-6) = 0, \ \zeta_{2}(-7) = -17/16$.
Apparently $\zeta_{2}$ vanishes at the negative even integers, while
$$
\frac{\zeta_{2}(-1)}{\zeta_{2}(2)} = \frac{1}{4}\cdot\frac{6\cdot 2}{\pi^2} =
\frac{3\cdot 1!}{1\cdot \pi^2}, \ \ \ \
\frac{\zeta_{2}(-3)}{\zeta_{2}(4)} =
-\frac{1}{8}\cdot\frac{30\cdot24}{7\pi^4} = -\frac{15\cdot 3!}{7\cdot \pi^4},
$$
$$
\frac{\zeta_{2}(-5)}{\zeta_{2}(6)} = \frac{1}{4}\cdot
\frac{42\cdot 6!}{31\pi^6} =
\frac{63 \cdot 5!}{31\cdot \pi^6}, \ \ \ \
\frac{\zeta_{2}(-7)}{\zeta_{2}(8)} = -\frac{17}{16}\cdot
\frac{30\cdot 8!}{127\cdot \pi^8}
 = -\frac{255\cdot 7!}{127\pi^8}.
$$
The numbers $1,
3, 7, 15, 31, 63, 127, 255$ are all one less than a power of 2,
so Euler was led to the observation that for $n \geq 2$,
$$
\frac{\zeta_{2}(1-n)}{\zeta_{2}(n)} =
\frac{(-1)^{n/2+1}(2^n-1)(n-1)!}{(2^{n-1}-1)\pi^n}
$$
if $n$ is even and
$$
\frac{\zeta_{2}(1-n)}{\zeta_{2}(n)} =
0
$$
if $n$ is odd. Notice how
the vanishing of $\zeta_{2}(s)$
at negative even integers nicely compensates for
the lack of knowledge of $\zeta_2(s)$ at positive odd integers $> 1$ (which
is the same as not knowing $\zeta(s)$ at positive odd integers $> 1$).
Euler interpreted the $\pm$ sign at even $n$ and the vanishing
at odd $n$ as the single factor $-\cos(\pi n/2)$, and with
$(n-1)!$ written as $\Gamma(n)$ we get
$$
\frac{\zeta_{2}(1-n)}{\zeta_{2}(n)} = -\Gamma(n)\frac{2^n-1}{(2^{n-1}-1)\pi^n}
\cos\left(\frac{\pi n}{2}\right).
$$
Writing $\zeta_{2}(n)$ as $(1 - 2^{1-n})\zeta(n)$ gives the
asymmetric functional
equation
$$
\frac{\zeta(1-n)}{\zeta(n)} = \frac{2}{(2\pi)^n}
\Gamma(n)\cos\left(\frac{\pi n}{2}\right).
$$
Euler applied similar ideas to $L(s,\chi_4)$ and found its
functional equation.  You can work this out yourself in
Exercise 2 below.
Exercises

Show that Euler's computation of zeta values at negative
integers can be put in the form
$$
(1 - 2^{n+1})\zeta(-n) =
\left.\left(u\frac{d}{du}\right)^{n}\right\vert_{u=1}\left(\frac{u}{1+u}
\right) = \left.\left(\frac{d}{dx}\right)^{n}\right\vert_{x=0}
\left(\frac{e^x}{1+e^x}\right).
$$
To compute the divergent series
$$
L(-n,\chi_4) = \sum_{j \geq 0} (-1)^{j}(2j+1)^n =
1 - 3^n + 5^n - 7^n - 9^n + 11^n - \dots
$$
for nonnegative integers $n$, begin with the formal identity
$$
\sum_{j \geq 0} X^{2j} = \frac{1}{1-X^2}.
$$
Differentiate and set $X = i$ to show $L(0,\chi_4) = 1/2$.
Repeatedly multiply by $X$, differentiate, and set
$X = i$ in order to compute $L(-n,\chi_4)$ for $0 \leq n \leq 10$. This computational technique is not rigorous, but the answers are correct. Compare with the values of $L(n,\chi_4)$ for positive $n$, if you know those, to get a formula for $L(1-n,\chi_4)/L(n,\chi_4)$. Treat alternating signs like special values of a suitable trigonometric function.


TITLE: The fiber of a Serre fibration
QUESTION [6 upvotes]: If $p:E\to B$ is a Serre fibration (assume it is surjective), then for each
$b\in B$  we get a comparison map $p^{-1}(b) \to F_b$, where $F_b$ is the homotopy
fiber of $p$ over $b$.
It is easy to see that these maps induce isomorphisms on $\pi_n$ for $n\geq 1$, but I
wonder about $\pi_0$.
Question:  Is it true that $p^{-1}(b) \to F_b$ is a weak homotopy
equivalence?

REPLY [2 votes]: Dear Jeff,
The map you describe is a homotopy equivalence. This is proved as Proposition 1.1 in the paper
Varadarajan, K. On fibrations and category.  Math. Z.  88  1965 267–273.


TITLE: Is it possible to assign probability to a set $X$ with $|X|>2^{\aleph_0}$?
QUESTION [4 upvotes]: Is it possible to assign probability to a set $X$ with cardinality $|X| > 2^{\aleph_0}$? Example would be a set $|X| = 2^{2^{\aleph_0}}$.

REPLY [3 votes]: For any cardinal $\kappa$, you can define the product measure on $2^{\kappa}$ where $0, 1$ are assigned one half measure each. This measure is defined on the sigma algebra generated by clopen subsets of $2^{\kappa}$. Let us call the corresponding measure algebra $\text{Random}(\kappa)$. The class of measure algebras thus obtained forms the building block for every atomless (probability) measure algebra in the following sense:
Theorem (Maharam): Every atomless (probability) measure algebra can be decomposed into countably many pieces each of which is isomorphic (modulo rescaling) to $\text{Random}(\kappa)$ for some $\kappa$.


TITLE: Please help me to determine whether it is linear !!!
QUESTION [0 upvotes]: For T: V2->V2
T maps each point with polar coordinate (r.theta) to each point with polar coordinate (r,2theta) and T maps 0 onto itself.
Hi,
I was trying to do this by letting r= square root of x^2 + y^2 and theta=arctan(y/x)
but I failed.
can anybody please explain it?

REPLY [0 votes]: We can deduce that $T$ is not linear because
$$
T[(1,0)] + T[(1,\pi)] = [(1,0) + (1,0)] = (2,0)
$$
But
$$
T[(1,0) + (1,\pi)] = T[0] = 0
$$


TITLE: Simplify a radical inside a radical inside a radical
QUESTION [1 upvotes]: The question is this:
Simplify $\sqrt{1+\sqrt{21+12\sqrt{3}}}$
I defined the value as x, then got $(x+1)^2(x-1)^2$=$21+12\sqrt{13}$.
I don't know what to do from there. Any help?

REPLY [2 votes]: Hint :
$$21+12 \sqrt{3} = (3+2\sqrt{3})^2$$
and
$$4 + 2 \sqrt{3} = (1 + \sqrt{3})^2$$


TITLE: Need help understanding Proposition 2.3.7 from Howie's Semigroups.
QUESTION [2 upvotes]: I don't understand the author's argument in the second line of the proof. In particular, I don't see exactly how such a bijection does exist.
I see that $ab \in L_b$ implies $H_b = H_{ab}$, and the bijection goes from $H_b$, but don't see how it goes onto $L_a \cap R_b$.

REPLY [1 votes]: By Green's Lemma, $\rho_c$ induces an $\mathcal R$-class preserving bijection from $L_b$ to $L_{bc}$. In particular $bc \in R_b$. Moreover since $L_{ab} = L_b$ and $\rho_c(ab) = abc = a\,$, one gets $L_{bc} = \rho_c(L_b) = \rho_c(L_{ab}) = L_{abc} = L_a\,$. Thus $bc \in L_a$ and finally $bc \in L_a \cap R_b$.


TITLE: Triangle wave equation
QUESTION [0 upvotes]: I have a triangle wave equation represented as
$$
y = \dfrac{A \cdot \left(P - \lvert\;\left(x \mod (2 \cdot P) \right) - P \;\rvert\right)}{P}
$$
where $A$ is the amplitude and $P$ is half of the period.
This equation starts at $(0,0)$. However, I would like the equation to start from an arbitrary point $(x,y)$. I can shift the wave vertically, but not horizontally. Is there any way to do that?
If it isn't possible with this equation, is there any general equation representing a Triangular wave with user defined starting point?

REPLY [0 votes]: First, look at this article in Wikipedia.
https://en.wikipedia.org/wiki/Sine_wave
Second, this equation is a starting point for the triangle wave.
sin y = cos x


TITLE: Can a positive binary quadratic form represent 14 consecutive numbers?
QUESTION [59 upvotes]: NEW CONJECTURE: There is no general upper bound.
Wadim Zudilin suggested that I make this a separate question. This follows
representability of consecutive integers by a binary quadratic form
where most of the people who gave answers are worn out after arguing over indefinite forms and inhomogeneous polynomials. Some real effort went into this, perhaps it will not be seen as a duplicate question.
So the question is, can a positive definite integral binary quadratic form
$$ f(x,y) = a x^2 + b x y + c y^2 $$
represent 13 consecutive numbers?
My record so far is 8: the form $$6x^2+5xy+14y^2 $$
 represents the 8 consecutive numbers from 716,234 to 716,241. Here we have discriminant $ \Delta = -311,$ and 2,3,5,7 are all residues $\pmod {311}.$ I do not think it remotely coincidental that $$6x^2+xy+13 y^2 $$ represents the 7 consecutive numbers from 716,235 to 716,241.
I have a number of observations. There is a congruence obstacle $\pmod 8$ unless, with
$ f(x,y) = a x^2 + b x y + c y^2 $  and $\Delta = b^2 - 4 a c,$ we have $\Delta \equiv 1 \pmod 8,$ or
$ | \Delta | \equiv 7 \pmod 8.$ If a prime $p | \Delta,$ then the form is restricted to either all quadratic residues or all nonresidues $ \pmod p$ among numbers not divisible by $p.$
In what could be a red herring, I have been emphasizing $\Delta = -p$ where $p \equiv 7 \pmod 8$ is prime, and where there is a very long string of consecutive quadratic residues $\pmod p.$ Note that this means only a single genus with the same $\Delta = -p,$ and any form is restricted to residues. I did not anticipate that long strings of represented numbers would not start at 1 or any predictable place and would be fairly large. As target numbers grow, the probability of not being represented by any form of the discriminant grows ( if prime $q \parallel n$ with $(-p| q) = -1$), but as the number of prime factors $r$ with $(-p| r) = 1$ grows so does the probability that many forms represent the number if any do.  Finally, on the influence of taking another $\Delta$ with even more consecutive residues, the trouble seems to be that the class number grows as well. So everywhere there are trade-offs.
EDIT, Monday 10 May. I had an idea that the large values represented by any individual form ought to be isolated. That was naive. Legendre showed that for a prime $q \equiv 7 \pmod 8$ there exists a solution to $u^2 - q v^2 = 2,$ and therefore infinitely many solutions. This means that the form $x^2 + q y^2$ represents the  triple of consecutive
numbers $q v^2, 1 + q v^2, u^2$ and then represents $4 + q v^2$ after perhaps skipping $3 + q v^2$.
Taking $q = 8 k - 1,$ the form $ x^2 + x y + 2 k y^2$ has no restrictions $\pmod 8,$ while an explicit formula shows that it represents every number represented by   $x^2 + q y^2.$ Put together, if $8k-1 = q$ is prime, then $ x^2 + x y + 2 k y^2$ represents infinitely many  triples. If, in addition, $ ( 3 | q) = 1,$ it seems plausible to expect infinitely many  quintuples. It should be admitted that the recipe given seems not to be a particularly good way to jump from length 3 to length 5, although strings of length 5 beginning with some $q t^2$ appear plentiful.
EDIT, Tuesday 11 May. I have found a string of 9, the form is $6 x^2 + x y + 13 y^2$ and the numbers start at $1786879113 = 3 \cdot 173 \cdot 193 \cdot 17839$ and end with
$1786879121$ which is prime. As to checking, I have a separate program that shows me the particular $x,y$ for representing a target number by a positive binary form. Then I checked those pairs using my programmable calculator, which has exact arithmetic up to $10^{10}.$
EDIT, Saturday 15 May. I have found a string of 10, the form is $9 x^2 + 5 x y + 14 y^2$ and the numbers start at $866988565 = 5 \cdot 23 \cdot 7539031$ and end with
$866988574 = 2   \cdot  433494287.$
EDIT, Thursday 17 June. Wadim Zudilin has been running one of my programs on a fast computer. We finally have a string of 11, the form being $ 3 x^2 + x y + 26 y^2$ of discriminant $-311.$ The integrally represented numbers start at  897105813710 and end at   897105813720. Note that the maximum possible for this discriminant is 11. So we now have this conjecture: For discriminants $\Delta$ with absolute values in this sequence
http://www.oeis.org/A000229
some form represents a set of $N$ consecutive integers, where $N$ is the first quadratic nonresidue. As a result, we conjecture that there is no upper bound on the number of consecutive integers that can be represented by a positive quadratic form.

REPLY [4 votes]: Here's a heuristic that suggests why arbitrarily large strings of consecutive
numbers should be representable by some binary quadratic form.  For simplicity
consider a prime $p$ that is $3\pmod 4$ so that $-p$ is a fundamental discriminant.  Suppose that $p$ has been chosen in such a way that all the primes $\le k$ are
quadratic residues $\pmod p$.  Suppose there are $h$ quadratic forms of discriminant $-p$ (and note that there is only one genus).
Recall that a number $n$ is represented by some form of discriminant $-p$ if
every prime factor $\ell$ of $n$ satisfies $\chi(\ell)=1$.  As discussed in my
answer to Achieving consecutive integers as norms from a quadratic field we should expect to find many strings of $k$ consecutive numbers, each of which is representable by some form of discriminant $-p$.
In my answer to that question, I focused on such strings of (almost) prime numbers,
but the same Hardy-Littlewood heuristics would predict lots of strings $n+1$, $\ldots$,
$n+k$ where each $n+j$ is divisible only by primes that are quadratic residues
$\pmod p$, and each $n+j$ has a typical number of prime factors.  Under the
restriction that all prime factors of $n$ are quadratic residues $\pmod p$, if $n$ is
large then typically it will have about $\frac 12 \log \log n$ such prime factors.  Moreover we may expect these prime factors to be roughly equally distributed
in the class group (which is of fixed size $h$).  Thus since there are $2^{\omega(n)}$
factorizations of $n$ as a product of two ideals, we would expect that typically there are many such factorizations with one of the factors lying in a prescribed
ideal class.
Summarizing one would expect that there are many strings $n+j$
($1\le j\le k$) with each $n+j$ composed of about $\frac 12\log \log n$ primes
that are all quadratic residues $\pmod p$, and (typically) each such $n+j$ would
be represented by every form of discriminant $-p$.
It should be possible with a little effort to turn this into a precise
Hardy-Littlewood type conjecture, but I don't see any hope of a proof.
The heuristic described above is probably classical.  One place where this
heuristic is described is a paper of Blomer and Granville: see pages 9 and 10 of
http://www.dms.umontreal.ca/~andrew/PDF/quadraticforms.pdf


TITLE: Calculate discount
QUESTION [1 upvotes]: This is my first question here, thus please have mercy. :)
I have minimum and maximum number of products and minimum and maximum price, and I want to calculate the discount depending of number of bought products.
minProducts = 1
maxProducts = 4000
minPrice = 0.8
maxPrice = 3.2

If they buy 4000 products then is the price 0.8 per product
if they buy 800 products then is the price 1.6 per product
and if they buy only one product then is the price 3.2.

How can I calculate the price per product if they buy for example 860 or 520 products?
Thanks in advance

REPLY [0 votes]: If they buy $800-3999$ products, then they pay half price ($\frac{3.2}{1.6} = \frac12$), so 50%.
If they buy $4000+$ products, they pay quarter price, so 25%.
EDIT: I may be reading this wrong. Is the discount different for say 800 and 850 products?
In that case, I (and WolframAlpha) is unable to find a function that fits these criteria. See examples:
Linear fit fails, as the points are not colinear.
Similarly, I attempted with quadratic fit, cubic fit, exponential fit, and logarithmic fit.
Note that the polynomial fits (quadratic and cubic) are able to hit the points perfectly, but they result in some weird discounts somewhere in between.


TITLE: Every torsion-free group is an abelian group?
QUESTION [2 upvotes]: Is it true that every torsion-free group (i.e. a group where the only element of finite order is the identity) is abelian?

REPLY [5 votes]: The Heisenberg group is torsion-free but not abelian. It is the set of matrices of the form
\begin{pmatrix}
 1 & a & c\\
 0 & 1 & b\\
 0 & 0 & 1\\
\end{pmatrix}
It is torsion-free because
$$
\begin{pmatrix}
 1 & a & c\\
 0 & 1 & b\\
 0 & 0 & 1\\
\end{pmatrix}^n
=
\begin{pmatrix}
 1 & na & {n \choose 2}ab+nc\\
 0 & 1 & nb\\
 0 & 0 & 1\\
\end{pmatrix}
$$
It is not abelian because $(AB)_{13} \ne (BA)_{13}$.


TITLE: If $x=\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{2015^2}$, show that $\frac{201}{403}<x<\frac{2014}{2015}$
QUESTION [7 upvotes]: If $$x=\frac{1}{2^2}+\frac{1}{3^2}+\cdots+\frac{1}{2015^2}$$
show that
$$\frac{201}{403}<x<\frac{2014}{2015}$$

So, I manage to do the RH inequality using that $$x<\frac{1}{2\cdot3}+\frac{1}{3\cdot4}+\cdots+\frac{1}{2014\cdot2015}=1-\frac{1}{2015}=\frac{2014}{2015}$$ Unfortunately I can't find a way to do the LH inequality. I saw that
$$\frac{1}{2015}+\frac{1}{2015}+\cdots+\frac{1}{2015}$$ for 1005 times is equal to $\frac{201}{403}$ but I don't see why
$$x> \frac{1}{2015}+\frac{1}{2015}+\cdots+\frac{1}{2015}$$ thx!

REPLY [6 votes]: We have the bound
$$\sum_{n=2}^{2015}\frac{1}{n^2}>\int_2^{2016}\frac{1}{x^2}dx=\frac{1}{2}-\frac{1}{2016}>\frac{1}{2}-\frac{1}{806}=\frac{402}{806}=\frac{201}{403}$$
by thinking about the graph of the function $y=1/x^2$ and noticing that if you draw rectangles of base length $1$ with four vertices $(n,0),(n+1,0),(n,1/n^2),(n+1,1/n^2)$ for $n=2,\dots,2015$ then the union of the resulting rectangles have an area bounded below by the integral given above.
By the way, this also works to establish the upper bound $2014/2015$.

REPLY [6 votes]: We have
$$\frac{1}{k}-\frac{1}{k+1} < \frac{1}{k^2} < \frac{1}{k-1} - \frac{1}{k}$$
and so (telescoping sum)
$$\frac{1}{2} - \frac{1}{2016} < \sum_{k=2}^{2015} \frac{1}{k^2} < \frac{1}{1} - \frac{1}{2015}$$
that is
$$\frac{1007}{2016}< \sum_{k=2}^{2015} \frac{1}{k^2} < \frac{2014}{2015}$$
Now,  LHS $= \frac{2014}{4032}= \frac{201.4}{403.2}> \frac{201}{403}$ (mediant)


text:
\begin{document}
\baselineskip=16pt

\begin{abstract}
Sharpening (a particular case of) a result of Szemer\'edi and Vu \refb{sv}
and extending earlier results of S\'ark\"ozy \refb{s} and ourselves
\refb{la}, we find, subject to some technical restrictions, a sharp threshold
for the number of integer sets needed for their sumset to contain a block of
consecutive integers of length, comparable with the lengths of the set
summands.

A corollary of our main result is as follows. Let $k,l\ge 1$ and $n\ge 3$ be
integers, and  suppose that $A_1\longc A_k\seq[0,l]$ are integer sets of size
at least $n$, none of which is contained in an arithmetic progression with
difference greater than $1$. If $k\ge2\lcl(l-1)/(n-2)\rcl$, then the sumset
$A_1\longp A_k$ contains a block of consecutive integers of length $k(n-1)$.
\end{abstract}

\maketitle

\section{Background and summary of results}

The \emph{sumset} of subsets $A_1\longc A_k$ of an additively written
group is defined by
  $$ A_1\longp A_k
               := \{ a_1\longp a_k\colon a_1\in A_1\longc a_k\in A_k \}; $$
if $A_1\longe A_k=A$, this is commonly abbreviated as $kA$. In the present
paper we will be concerned exclusively with the group of integers, in which
case a well-known phenomenon occurs: if all sets $A_i$ are dense, and their
number $k$ is large, then the sumset $A_1\longp A_k$ contains long arithmetic
progressions. There are numerous ways to specialize this statement,
indicating the exact meaning of ``dense'', ``large'', and ``long'', but in
our present context the following result of S\'ark\"ozy is the origin of
things.

\begin{theorem}[\protect{S\'ark\"ozy \cite[Theorem~1]{b:s}}]\label{t:sarkozy}
Let $l\ge n\ge 2$ be integers, and write $\kap:=\lcl(l+1)/(n-1)\rcl$. Then,
for every integer set $A\seq[1,l]$ with $|A|=n$, there exist positive
integers $d\le\kap-1$ and $k<118\kap$ such that the sumset $kA$ contains $l$
consecutive multiples of $d$.
\end{theorem}

In \refb{la} we established a sharp version of this result, replacing the
factor $118$ with $2$ (which is the best possible value, as conjectured by
S\'ark\"ozy) and indeed, going somewhat further.
\begin{theorem}[\protect{Lev \cite[Theorem~1]{b:la}}]\label{t:lev}
Let $n\ge 3$ and $l\ge n-1$ be integers, and write
$\kap:=\lfl(l-1)/(n-2)\rfl$. Then for every integer set $A\seq[0,l]$ with
$0,l\in A,\ \gcd(A)=1$, and $|A|=n$, and every integer $k\ge 2\kap$, we have
  $$ [\kap(2l-2-(\kap+1)(n-2)), kl-\kap(2l-2-(\kap+1)(n-2))] \seq kA. $$
\end{theorem}

The complicated-looking interval appearing in the statement of Theorem
\reft{lev} is best possible and, in general, cannot be extended even by $1$
in either direction. As the interested reader will easily check, this
interval (strictly) includes $[\kap l,(k-\kap)l]$ as a subinterval;
consequently, if $k\ge 2\kap+1$, then its length exceeds $l$. At the same
time, if $k\le 2\kap$, then the sumset $kA$ may fail to contain a block of
consecutive integers of length $l$; see example below. Thus, $2\kap+1$ is the
smallest value of $k$ such that, with $A$ as in Theorem \reft{lev}, the
sumset $kA$ is guaranteed to contain a block of consecutive integers of
length $l$.

At first sight, Theorem \reft{lev} is weaker than Theorem \reft{sarkozy} in
imposing the extra assumptions $0,l\in A$ and $\gcd(A)=1$. It is explained in
\refb{la}, however, that these assumptions are merely of normalization
nature, and a refinement of Theorem \reft{sarkozy}, with the bound $118\kap$
replaced by $2\kap+2$ (and some other improvements), is deduced from Theorem
\reft{lev} in a relatively straightforward way.

We notice that Theorem \reft{lev} yields a sharp result about the function
$f(n,k,l)$, introduced in \refb{sv}. This function is defined for positive
integers $k$ and $l\ge n\ge 2$ to be the largest number $f$, such that for
every $n$-element integer set $A\seq[1,l]$, the sumset $kA$ contains an
arithmetic progression of length $f$. (The \emph{length} of an arithmetic
progression is the number of its terms, less $1$). As indicated in \refb{sv},
``many estimates for $f(n,k,l)$ have been discovered by Bourgain, Freiman,
Halberstam, Green, Ruzsa, and S\'ark\"ozy''. It is worth noting in this
connection that Theorem \reft{lev} establishes the \emph{exact value} of this
function for $k$ large; namely, it is easy to deduce from Theorem \reft{lev}
(and keeping in mind the trivial example $A=[1,n]$) that
  $$ f(n,k,l)=k(n-1);\quad k\ge 2\lfl(l-2)/(n-2)\rfl+2. $$
This, to our knowledge, remains the only situation where the value of
$f(n,k,l)$ is known precisely.

An obvious shortcoming of Theorem \reft{lev} is that it applies only to
identical set summands. Potentially distinct summand are dealt with by
Szemer\'edi and Vu in \refb{sv}. A particular case of their result, to be
compared with Theorems \reft{sarkozy} and \reft{lev}, is as follows.
\newpage
\begin{theorem}[Szemer\'edi-Vu
      \protect{\cite[particular case of Corollary 5.2]{b:sv}}]\label{t:szvu}
There exist positive absolute constants $C$ and $c$ with the following
property. Suppose that $k,l\ge 1$ and $n\ge 2$ are integers, and
 $A_1\longc A_k\seq[0,l]$ are integer sets, having at least $n$ elements each.
If $k>Cl/n$, then the sumset $A_1\longp A_k$ contains an arithmetic
progression of length at least $ckn$.
\end{theorem}

Though the proof of Theorem \reft{szvu}, presented in \refb{sv}, is
constructive, the constants $C$ and $c$ are not computed explicitly. Indeed,
the argument leads to excessively large values of these constants, which may
present a problem in some applications.

The goal of this note is to merge the best of the two worlds, extending
Theorem \reft{lev} onto distinct set summands, or, equivalently, proving a
sharp analogue if Theorem \reft{szvu}, with $Cl/n$ and $ckn$ replaced with
best possible expressions. A result of this sort (up to a technical
restriction, addressed below) is an almost immediate corollary from the
following theorem, proven in Section \refs{proofs}.
\begin{theorem}\label{t:main}
Let $k,l\ge 1$ and $n\ge 3$ be integers, and write
$\kap:=\lcl(l-1)/(n-2)\rcl-1$. Suppose that $A_1\longc A_{2\kap+1}\seq[0,l]$
are integer sets, having at least $n$ elements each, and such that none of
them are contained in an arithmetic progression with difference greater than
$1$. Then the sumset $A_1\longp A_{2\kap+1}$ contains a block of consecutive
integers of length $2(\kap+1)(n-1)-l>l$.
\end{theorem}

Observe, that Theorem \reft{main} guarantees the existence of a block of
consecutive integers of length $l$ in $A_1\longp A_k$ for $k=2\kap+1$, which
is a sharp threshold: for $k=2\kap$ the sumset may fail to contain such a
block, as witnessed, say, by the system of identical sets
  $$ A_1\longe A_{2\kap}=[0,m]\cup[l-m,l] $$
with $m\in[1,l/2)$ integer and $n=2m+2$. Indeed, in this case we have
  $$ A_1\longp A_{2\kap}
                      = \bigcup_{j=0}^{2\kap} \, [j(l-m),j(l-m)+2\kap m], $$
the length of each individual segment being $2\kap m=\kap(n-2)<l$, and the
segments not abutting, provided $\{(l-1)/(n-2)\}>1/2$.

Unfortunately, we were unable to eliminate the assumption that none of the
sets $A_j$ are contained in an arithmetic progression with difference greater
than $1$. This reminiscent of the condition $\gcd(A)=1$ from Theorem
\reft{lev} will be discussed in Section \refs{conclusion}.

The reader may compare the following corollary against Theorem \reft{szvu}.
\newpage
\begin{corollary}\label{c:main}
Suppose that $k,l\ge 1$ and $n\ge 3$ are integers, and
 $A_1\longc A_k\seq[0,l]$ are integer sets, having at least $n$ elements
each, and such that none of them are contained in an arithmetic progression
with difference greater than $1$. If $k\ge 2\lcl(l-1)/(n-2)\rcl$, then the
sumset $A_1\longp A_k$ contains a block of consecutive integers of length
$k(n-1)$.
\end{corollary}

\begin{proof}
Reducing the value of $l$ and renumbering the sets, if necessary, we can
assume that $0,l\in A_k$. Write $\kap:=\lcl(l-1)/(n-2)\rcl-1$. By Theorem
\reft{main}, the sumset $A_1\longp A_{2\kap+1}$ contains a block of
consecutive integers of length at least $2(\kap+1)(n-1)-l>l$. Adding one by
one the sets $A_{2\kap+2}\longc A_{k-1}$ to this sumset, we increase the
length of the block by at least $n-1$ each time, and adding $A_k$ at the last
step we increase the length by $l$. Consequently, $A_1\longp A_k$ contains a
block of length at least
  $$  (2(\kap+1)(n-1)-l) + (k-2\kap-2)(n-1) + l = k(n-1). $$
\end{proof}

\section{Proof of Theorem \reft{main}}\label{s:proofs}

For a finite, non-empty integer set $A$ let $\ell(A)$ denote the difference
of the largest and the smallest elements of $A$.

Our approach is fairly close to that employed in \refb{la}, with the
following result in its heart.
\begin{theorem}[Lev \protect{\cite[Theorem~1]{b:lb}}]\label{t:sumsetgrowth}
Let $k\ge 2$ be an integer, and suppose that $A_1\longc A_k$ are finite,
non-empty integer sets. If $\ell(A_j)\le\ell(A_k)$ for $j=1\longc k-1$ and
$A_k$ is not contained in an arithmetic progression with difference greater
than $1$, then
  $$ |A_1\longp A_k| \ge |A_1\longp A_{k-1}|
                            + \min \{ \ell(A_k),\, n_1\longp n_k-k+1 \}, $$
where
  $$ n_j = \begin{cases}
             |A_j| &\text{ if }\ \ell(A_j)<\ell(A_k) \\
             |A_j|-1 &\text{ if }\ \ell(A_j)=\ell(A_k)
           \end{cases}; \quad j=1\longc k. $$
\end{theorem}

Up to some subtlety which we suppress for the moment, the strategy pursued
below is to apply Theorem \reft{sumsetgrowth} to show that if $k$ is large
enough (which in practice means $k\ge 2\kap+O(1)$), then the densities of the
sumsets $A_1\longp A_{\lfl k/2\rfl}$ and $A_{\lfl k/2\rfl+1}\longp A_k$
exceed $1/2$, and then use the box principle to conclude that the sumset of
the two, which is $A_1\longp A_k$, contains a long block of consecutive
integers. We start with the second, technically simpler, component.

\begin{lemma}\label{l:box}
Let $L_1$ and $L_2$ be positive integers and suppose that $S_1\seq[0,L_1]$
and $S_2\seq[0,L_2]$ are integer sets. If $\max\{L_1,L_2\}\le |S_1|+|S_2|-2$,
then
  $$ [L_1+L_2-(|S_1|+|S_2|-2),|S_1|+|S_2|-2] \seq S_1+S_2. $$
\end{lemma}

\begin{proof}
Given an integer $g\in[0,L_1+L_2]$, the number of representations $g=s_1+s_2$
with arbitrary $s_1\in[0,L_1]$ and $s_2\in[0,L_2]$ is
\begin{align*}
  |(g-[0,L_1]) \cap [0,L_2]|
    &= |[g-L_1,g] \cap [0,L_2]| \\
    &= \min\{g,L_2\} - \max\{g-L_1,0\} + 1 \\
    &= \min\{g,L_2\} + \min\{g,L_1\} - g + 1.
\end{align*}
In order for $g\in S_1+S_2$ to hold, it suffices that this number of
representations exceeds the total number of ``gaps'' in $S_1$ and $S_2$; that
is,
  $$ \min\{g,L_2\} + \min\{g,L_1\} - g + 1 > L_1+L_2+2-|S_1|-|S_2|. $$
This, however, follows immediately for every $g$ in the interval
$[L_1+L_2-(|S_1|+|S_2|-2),|S_1|+|S_2|-2]$, by considering the location of $g$
relative to $L_1$ and $L_2$.
\end{proof}

\begin{comment}
\begin{proof}
Assume for definiteness that $L_1\le L_2$, and let $g$ be an integer.

If $L_1+L_2-(|S_1|+|S_2|-2)\le g\le L_1$, then
\begin{multline*}
 |(g-S_1)\cap[0,g]| + |S_2\cap[0,g]| \\
                        \ge (g+1-(L_1+1-|S_1|)) + (g+1-(L_2+1-|S_2|)) > g+1,
\end{multline*}
whence $g-S_1$ and $S_2$ have non-empty intersection and therefore
 $g\in S_1+S_2$.

If $L_1\le g\le L_2$, then both $g-S_1$ and $S_2$ are subsets of $[0,L_2]$
and
  $$ |g-S_1|+|S_2| = |S_1|+|S_2| > L_2+1, $$
whence $g\in S_1+S_2$ as above.

Finally, if $L_2\le g\le |S_1|+|S_2|-2$, then
  $$ |(g-S_1)\cap[0,L_2]| + |S_2| \ge (|S_1|-(g-L_2)) + |S_2| > L_2+1, $$
implying $g\in S_1+S_2$ in this case, too.
\end{proof}
\end{comment}

We now turn to the more technical part of the argument, consisting in
inductive application of Theorem \reft{sumsetgrowth}.
\begin{proposition}\label{p:ind}
Let $k,l\ge 1$, and $n\ge 3$ be integers, and suppose that $A_1\longc A_k$
are integer sets with $|A_i|\ge n$ and $\ell(A_i)\le l$ for $i=1\longc k$,
such that none of these sets are contained in an arithmetic progression with
difference greater than $1$. Write $S=A_1\longp A_k$.
\begin{itemize}
\item[(i)]  If $k\ge (l-1)/(n-2)-1$, then
  $|S|\ge\frac12\,(\ell(S)+(k+1)(n-1)-l+2)$;
\item[(ii)] if $k\ge (l-1)/(n-2)$, then $|S|\ge\frac12\,(\ell(S)+k(n-1)+2)$.
\end{itemize}
\end{proposition}

Observe, that under assumption (i) we have $(k+1)(n-1)-l+2>0$, so that
$|S|>\ell(S)/2$ in this case. Similarly, under assumption (ii) we have
$k(n-1)+2>l$, and hence in this case the stronger estimate
$|S|>(\ell(S)+l)/2$ holds.

\begin{proof}[Proof of Proposition \refp{ind}]
Write $l_j=\ell(A_j)$. Without loss of generality, we can assume that
$l_1\longle l_k$. By Theorem \reft{sumsetgrowth} and in view of
$\ell(S)=l_1\longp l_k$, we have
\begin{align}
  |S|-\frac12\,\ell(S)
     &\ge \sum_{j=1}^k \big( \min \{ l_j-1,j(n-2) \}  + 1 \big) + 1
                                   - \frac12\,(l_1\longp l_k) \notag \\
     &=   \sum_{j=1}^k \min \lfr \frac{l_j-1}2, j(n-2)-\frac{l_j-1}2 \rfr
           + \frac k2\,+1. \label{e:sum}
\end{align}

Starting with assertion (ii), assume that $k\ge(l-1)/(n-2)$. Color all
integers $j\in[1,k]$ red or blue, according to whether $l_j-1\ge j(n-2)$ or
$l_j-1<j(n-2)$. Notice that the integer $1$ is then colored red, hence the
interval $[1,k]$ can be partitioned into a union of adjacent subintervals
$J_1\longu J_K$ so that each subinterval consists of a block of consecutive
red integers followed by a block of consecutive blue integers, with all
blocks non-empty --- except that the rightmost subinterval $J_K$ may consist
of a ``red block'' only. Accordingly, we write the sum over $j\in[1,k]$ in
the right-hand side of \refe{sum} as $\sig_1\longp \sig_K$, where for each
$\nu\in[1,K]$ by $\sig_\nu$ we denote the sum over all $j\in J_\nu$.

Fixing $\nu\in[1,K]$, write $J_\nu=[s,t]$ and define $q$ to be the largest
red-colored number of the interval $[s,t-1]$. This \emph{does not} define $q$
properly if $\nu=K$ and $s=t=k$; postponing the treatment of this exceptional
case, suppose for the moment that $q$ is well defined. Thus either $q+1$ is
blue, whence $l_{q+1}-1<(q+1)(n-2)$, or $\nu=K,\,t=k$, and $q=k-1$, whence
  $$ l_{q+1}-1=l_k-1\le l-1\le k(n-2)=(q+1)(n-2). $$
Observe, that
\begin{equation}\label{e:lq+1}
  l_{q+1}-1 \le (q+1)(n-2)
\end{equation}
holds in either case, and it follows that
\begin{align*}
  \sig_\nu &=   \sum_{j=s}^q \lpr j(n-2)-\frac{l_j-1}2\rpr
                                          + \sum_{j=q+1}^t \frac{l_j-1}2 \\
           &\ge \frac{n-2}2 \, (q^2+q-s^2+s) - \frac{l_q-1}2 \, (q+1-s)
                                                + \frac{l_q-1}2 \, (t-q) \\
           &=   \frac{n-2}2 \, (q^2+q-s^2+s) + \frac{l_q-1}2 \, (s+t-1-2q).
\end{align*}
We now distinguish two cases: $q\le(s+t-1)/2$ and $q\ge(s+t-1)/2$. In the
former case we have
\begin{align*}
  \sig_\nu &\ge \frac{n-2}2\,(q^2+q-s^2+s+q(s+t-1-2q)) \\
           &=   \frac{n-2}2\,(q(s+t-q)-s^2+s) \\
           &=   \frac{n-2}2\,(st+(q-s)(t-q)-s^2+s) \\
           &\ge \frac{n-2}2\,(st-s^2+s) \\
           &=   \frac{n-2}2\,s|J_\nu|.
\end{align*}
In the latter case, taking into account that
 $l_q-1\le l_{q+1}-1\le (q+1)(n-2)$ by \refe{lq+1}, we obtain the same
estimate:
\begin{align*}
  \sig_\nu &\ge \frac{n-2}2\,(q^2+q-s^2+s+(q+1)(s+t-1-2q)) \\
           &=   \frac{n-2}2\,(q(s+t-2-q)-s^2+2s-1+t) \\
           &\ge \frac{n-2}2\,((t-1)(s-1)-s^2+2s-1+t) \\
           &=   \frac{n-2}2\,(st-s^2+s) \\
           &=   \frac{n-2}2\,s|J_\nu|.
\end{align*}
Addressing finally the situation where $\nu=K$ and $s=t=k$, we observe that
in this case
\begin{align*}
  \sig_\nu &=   k(n-2) - \frac{l_k-1}2 \\
           &\ge k(n-2) - \frac{l-1}2 \\
           &\ge \frac{k(n-2)}2 \\
           &=   \frac{n-2}2\,s|J_\nu|,
\end{align*}
as above. Thus,
  $$ \sig_1\longp\sig_K \ge \frac{n-2}{2}\ \big( |J_1|\longp|J_K| \big)
                                                  = k \, \frac{n-2}{2}, $$
and substituting this into \refe{sum} we obtain assertion (ii).

To prove assertion (i), instead of $k\ge(l-1)/(n-2)$ assume now the weaker
bound $k\ge(l-1)/(n-2)-1$. Set $l_{k+1}=l_k$, so that $l_{k+1}-1\le
l-1\le(k+1)(n-2)$. From \refe{sum} we get
  $$ |S|-\frac12\,\ell(S)
       \ge \sum_{j=1}^{k+1} \min \lfr \frac{l_j-1}2, j(n-2)-\frac{l_j-1}2 \rfr
                                       - \frac{l_{k+1}-1}2 + \frac k2\,+1. $$
Since $k+1\ge (l-1)/(n-2)$, the sum over $j$ can be estimated as above, and
it is at least $(k+1)(n-2)/2$. Assertion (i) now follows in view of
\begin{multline*}
  \frac{(k+1)(n-2)}2-\frac{l_{k+1}-1}2+\frac k2+1 \\
         \ge \frac12\,\big( (k+1)(n-2) - (l-1) + k + 2\big)
                  = \frac12\,\big( (k+1)(n-1) - l + 2 \big).
\end{multline*}
\end{proof}

Proposition \refp{ind} took us most of the way to the proof of Theorem
\reft{main}.
\begin{proof}[Proof of Theorem \reft{main}]
Assume that the sets $A_1\longc A_{2\kap+1}$ are so numbered that, letting
$l_j=\ell(A_j)$ for $j\in[1,2\kap+1]$, we have
 $l_1\ge l_2\longge l_{2\kap+1}$. We are going to partition our sets into two
groups to apply Lemma \refl{box} to the sumsets $S_1$ and $S_2$ of these
groups, and this is to be done rather carefully as effective application of
the lemma requires that $S_1$ and $S_2$ be of nearly equal length.

Accordingly, we let $S_1:=A_1+A_3\longp A_{2\kap-1}$ (including all sets
$A_j$ with odd indices $j<2\kap$) and
 $S_2:=(A_2+A_4\longp A_{2\kap})+A_{2\kap+1}$ (all sets $A_j$ with even
indices $j\le 2\kap$ and $A_{2\kap+1}$). By Proposition \refp{ind} we have
\begin{align}
  |S_1| &\ge \frac12\,(\ell(S_1)+(\kap+1)(n-1)-l+2) \label{e:sls1} \\
\intertext{and}
  |S_2| &\ge \frac12\,(\ell(S_2)+(\kap+1)(n-1)+2). \label{e:sls2}
\end{align}
Furthermore, from
  $$ \ell(S_1)-\ell(S_2)=(l_1-l_2)\longp(l_{2\kap-1}-l_{2\kap})
                                                  -l_{2\kap+1}\in[-l,l], $$
using \refe{sls1} and \refe{sls2} we get
\begin{multline*}
  \max \{ \ell(S_1),\ell(S_2) \} \le \frac12\,(\ell(S_1)+\ell(S_2)+l) \\
    \le |S_1|+|S_2| +l - (\kap+1)(n-1) -2 \le |S_1|+|S_2| - 2.
\end{multline*}
Applying Lemma \refl{box} and using again \refe{sls1} and \refe{sls2}, we
conclude that $A_1\longp A_k=S_1+S_2$ contains a block of consecutive
integers of length at least
  $$ 2(|S_1|+|S_2|-2) - (\ell(S_1)+\ell(S_2))
       \ge 2(\kap+1)(n-1) -l , $$
as required.
\end{proof}

\section{Concluding remarks and open problems}\label{s:conclusion}

The major challenge arising in connection with the main results of this paper
(which are Theorem \reft{main} and Corollary \refc{main}) is to get rid of
the assumption that none of the sets involved are contained in an arithmetic
progression with difference greater than $1$. One can expect that a vital
ingredient of such an improvement would be a suitable generalization of
Theorem \reft{sumsetgrowth}. Indeed, we were able to generalize Theorem
\reft{sumsetgrowth} in what seems to be the right direction.
\begin{primetheorem}\label{t:classes}
Let $k\ge 2$ be an integer, and let $A_1\longc A_k$ be finite, non-empty
integer sets. Suppose that $l\in A_k-A_k$ is a positive integer, and define
$d$ to be the largest integer such that $A_k$ is contained in an arithmetic
progression with difference $d$. Then
  $$ |A_1\longp A_k| \ge |A_1\longp A_{k-1}|
                              + \min \{ hl/d,\, n_1\longp n_k-k+1 \}, $$
where $h$ is the number of residue classes modulo $d$, represented in
$A_1\longp A_{k-1}$, and $n_j\ (j=1\longc k)$ is the number of residue
classes modulo $l$, represented in $A_j$.
\end{primetheorem}

Clearly, Theorem \reft{classes} implies Theorem \reft{sumsetgrowth} and,
furthermore, shows that the assumption of Theorem \reft{main} that none of
the sets $A_j$ are contained in an arithmetic progression with difference
greater than $1$ can be slightly relaxed. Specifically, it suffices to
request that the $A_j$ can be so ordered that $\ell(A_j)$ increase, and for
every $k\in[1,2\kap]$ the sumset $A_1\longp A_k$ represents all residue
classes modulo $\gcd(A_{k+1}-A_{k+1})$. It seems, however, that Theorem
\reft{classes} by itself fails short to extend Theorem \reft{main} the
desired way, dropping the modular restriction altogether, and in the absence
of an application we do not present here the proof of the former theorem.

Another interesting direction is to refine Theorem \reft{main} as to the
length of the block, contained in the sumset $A_1\longp A_{2\kap+1}$. While
we observed that $2\kap+1$ is the smallest number of summands which ensures a
block of length $l$, it is quite possible that the existence of a longer
block can be guaranteed. In this connection we mention the following
conjecture from \refb{la}, referring to the equal summands situation.
\begin{conjecture}\label{j:lint}
Let $k,l\ge 1$ and $n\ge 3$ be integers, and write
$\kap:=\lfl(l-1)/(n-2)\rfl$. Suppose that $A\seq[0,l]$ is an integer set with
$0,l\in A,\,\gcd(A)=1$, and $|A|=n$. If $k\ge 2\kap+1$, then $kA$ contains a
block of consecutive integers of length $(k-\kap)l+k((\kap+1)(n-2)+2-l)$.
\end{conjecture}
In fact, Conjecture \refj{lint} is established in \refb{la} in the case where
$k\ge 3\kap$, but the case $2\kap+1\le k<3\kap$, to our knowledge, remains
open.

\vfill

config: arxiv


text:
\begin{document}
\title{The pebbling threshold of the square of cliques}
\author{A. Bekmetjev}
\address{A. Bekmetjev\\ Department of Mathematics \\ Hope College\\ Holland, MI 49422-9000}
\email{bekmetjev@hope.edu}
\author{G. Hurlbert \thanks{}}
\address{G. Hurlbert\\ Department of Mathematics and Statistics \\ Arizona State University\\ Tempe, AZ 85287-1804}
\email{hurlbert@asu.edu}

\thanks{$^*$ Partially supported by National Security Agency grant
\#MDA9040210095.}
\date{December 30, 2003}
\subjclass{Primary 05C35, 00A43; Secondary 05C80, 60C05}
\keywords{pebbling, threshold, product of graphs, random configuration}
\maketitle
\begin{abstract}
Given an initial configuration of pebbles on a graph, one can move pebbles
in pairs along edges, at the cost of one of the pebbles moved, with the
objective of reaching a specified target vertex.
The pebbling number of a graph is the minimum number of pebbles so that
every configuration of that many pebbles can reach any chosen target.
The pebbling threshold of a sequence of graphs is roughly the number of
pebbles so that almost every (resp. almost no) configuration of asymptotically
more (resp. fewer) pebbles can reach any chosen target.
In this paper we find the pebbling threshold of the sequence of
squares of cliques, improving upon an earlier result of Boyle and
verifying an important instance of a probabilistic version of
Graham's product conjecture.
\end{abstract}

\section{Pebbling Number}

Consider a connected graph $G$ on $n$ vertices. Suppose that a
\emph{configuration} $C$ of $t$ pebbles is
placed onto the vertices of graph $G.$
A\emph{\ pebbling step\ }from $u$ to $v$ consists of removing two
pebbles from vertex $u$\ and then placing one pebble on an adjacent vertex $
v $\emph{. }We say that a pebble can be \textit{moved} to a vertex $r$
(called \textit{root} vertex) if after finitely many steps $r$ has at least
one pebble.\emph{\ }If it is possible to move a pebble to the root vertex $r$
\ then we say that $C$\ is $r$\emph{-solvable}; otherwise, $C$\ is $r$\emph{
-unsolvable}. Finally, we call $C$\ \emph{solvable}\ if it is $r$-solvable
for all $r$, and \emph{unsolvable}\ otherwise. Define
the \emph{pebbling number}\ $\pi (G)$\ to be the smallest integer $t$\ such
that every configuration of $t$\ pebbles on the vertices of $G$\ is solvable.
A fair amount is known about the pebbling numbers of typical graphs like
complete graphs, paths, cycles, cubes, etc. (see \cite{hurl} for a survey),
relations to known parameters such as connectivity \cite{chkt},
diameter \cite{bukh}, girth \cite{ch}, and domination number \cite{changod},
and interesting variations such as optimal pebbling \cite{moewsopt}, and
cover pebbling \cite{ccfhpst} are being investigated.

\section{Random Configurations}

In this paper we consider a random pebbling model in which a particular
configuration of pebbles is selected uniformly at random from the set of all
configurations with a fixed number of pebbles. One can think of the configuration of pebbles as a placement of unlabeled balls in
labeled distinct urns. This is analogous to the so-called \emph{static} model
of random graphs, whose sample space consists of all graphs with a fixed
number of edges. Since vertices may have more than one
pebble, a particular configuration is a multiset of $t$ elements with the
ground set $[n]$. We construct the probability space $\mathbf{C}_{n,t}$ by
choosing configurations randomly and assuming that they all are equally
likely to occur.

The size of the set $\mathbf{C}_{n,t}$ is the number of possible
arrangements of $t$ identical balls placed in $n$ distinct urns, so $|
\mathbf{C}_{n,t}|={\binom{n+t-1}{t}}$, which we denote by
$\QATOPD\langle \rangle {n}{t}$ (the reader may find it useful to use the
terminology ``$n$ \textit{pebble} $t$''). We will be interested in the
probability spaces associated with sequences of graphs $\mathcal{G}
=(G_{1},G_{2},\ldots ,G_{n},\ldots ).$ In this notation the index $n$
represents the position of the graph $G_{n}.$ In some of the graph
sequences, such as cubes, for example, the size of the vertex set of $G_{n}$
is not the same as the position. Therefore, we define $N=N_n=N(G_n)=|V(G)|$
to be the number of vertices of $G_n$. Graphs in $\mathcal{G}$ are in
ascending order with respect to this number, i.e. $N_n>N_m$ for $n>m$.

We will study the pebbling threshold phenomenon that occurs in this model,
as it does for many random graph properties. For two functions $f(n)$\ and $
g(n)$\ we write $f\ll g$, (equivalently $g\gg f$\ ) if
$\lim_{n\rightarrow\infty} f(n)/g(n)=0$.
We set $o(g)=\{f$\ $|$\ $f\ll g\}$\ and $
\omega (f)=\{g$\ $|$\ $f\ll g\}$. Also, we write $f\in O(g)$, or
equivalently $g\in \Omega (f),$ when there are positive constants $c$\ and $
k$\ such that $f(n)/g(n)<c$, for all $n>k$.\ In particular, if$\
f(n)/g(n)\rightarrow 1$ as $n\rightarrow \infty$, we write $
f\thicksim g$. Furthermore, we define $\Theta (g)$\ $=$\ $O(g)\cap \Omega
(g)$. Finally, for two sets of functions $F$ and $G$\ we write $F\lesssim G$
\ if $f\in O(g)$ for all $f\in F,g\in G$\textbf{.}

A function $f=f(n)$\ is called a\emph{\ threshold\ }for the graph sequence $
\mathcal{G}$, and we write\emph{\ }$f\in \tau _{\mathcal{G}}$\emph{, }if
$P_{\mathcal{G}}(n,t)\rightarrow 1$ whenever $t\gg f,$ and $P_{\mathcal{G}
}(n,t)\rightarrow 0,$ whenever\emph{\ }$t\ll f.$\emph{\ }
In other words, if $f=f(n)\in \tau _{\mathcal{G}}$,
then for any function $\varpi
=\varpi (n)$ tending to infinity with $n$, $P_{\mathcal{G}}(n,\varpi
f)\rightarrow 1$ and $P_{\mathcal{G}}(n,f/\varpi )\rightarrow 0$ as\emph{\ }
$n\rightarrow \infty $.

Roughly speaking, the pebbling number describes the ``worst-case'' scenario,
as it is one more than the size of the largest unsolvable configuration.
The threshold function, on the
other hand, deals with ``typical'' configurations and estimates the
average chance of being solvable. For example, the
threshold of family of cliques $\mathcal{K}$ is $\tau _{\mathcal{K}
}=\Theta (\sqrt{N}).$ This problem is similar to the well-known ``birthday''
problem ---
how many people must be in a room so that with high probability two people
share the same birth date?
--- but here the pebbles are unlabelled.  The
general existence of the pebbling threshold is established in \cite{thres},
and in \cite{cehk} it is shown that every graph sequence $\mathcal G$ satisfies
$\tau_{\mathcal G}\subset \Omega(f)\cap O(g)$, where $f\in\tau_{\mathcal K}$
and $g\in\tau_{\mathcal P}$, for the sequence of paths ${\mathcal P}$.
We are going to compute the pebbling threshold of the sequence of
squares of cliques, thereby verifying an instance of the threshold analogue
of Graham's product conjecture.

\section{Cartesian Products and Graham's Conjecture}

Chung's paper \cite{chung} raised a natural question about the relationship
between the pebbling numbers of individual graphs and the pebbling number of
their cartesian product.

\begin{definition}
\emph{The} Cartesian product\emph{\ of two graphs }$G_{1}$\emph{\ and }$
G_{2},$\emph{\ denoted }$G_{1}\Box G_{2}$\emph{\ is the graph with }$\emph{
vertex\ set}$\emph{\ }

\begin{equation*}
V(G_{1}\Box G_{2})=\{(v_{1},v_{2})\text{ }|\text{ }v_{1}\in
V(G_{1}),v_{2}\in V(G_{2})\}
\end{equation*}
\emph{and }$\emph{edge\ set}$
\begin{equation*}
\begin{tabular}{lll}
$E(G_{1}\Box G_{2})$ & $=$ & $\{$ $((v_{1},v_{2}),(w_{1},w_{2}))$ $|$ $
v_{1}=w_{1}\text{\emph{ and} }(v_{2},w_{2})\in E(G_{2})$ \emph{or} \\
&  & $\qquad \qquad \quad \quad \qquad $\emph{\ \ \ \ \ }$v_{2}=w_{2}\text{
\emph{ and }}(v_{1},w_{1})\in E(G_{1})$ $\}$\ .
\end{tabular}
\end{equation*}
\emph{\ }
\end{definition}

The general conjecture about the pebbling number of the cartesian product of
graphs was originally stated by Graham (\cite{chung}).
\begin{conjecture}
\label{graham}
For all graphs $G_{1}$ and $G_{2}$ we have that
\begin{equation*}
\pi (G_{1}\Box G_{2})\leqslant \pi (G_{1})\pi (G_{2})\ .
\end{equation*}
\end{conjecture}
There are several results supporting this conjecture. It is known \cite{chung}
that the $m$-dimensional cube and that the product of cliques satisfy
this conjecture.
Also, Moews \cite{moews} proved it holds for the product of trees.
Pachter et al. \cite{pachter} proved the conjecture for the product of
cycles with some exceptions: it holds for $C_{m}\Box C_{n}$ where $m$ and $n$
are not both from the set $\{5,7,9,11,13\}$. Herscovici and Higgins in \cite
{higgins} proved it for $C_{5}\Box C_{5}$. Recently, Herscovici \cite
{higginsnew} found a proof for all these exceptions confirming Graham's
conjecture for the product of cycles.
Finally, the conjecture holds for dense graphs \cite{ch}.

\section{\label{secprobgraham} Threshold Version and Main Theorem}

For the graph sequences ${\mathcal G}=(G_{1},\ldots G_{n},\ldots )$ and
${\mathcal H}=(H_{1},\ldots ,H_{n},\ldots )$ let us define the sequence
${\mathcal G}\Box{\mathcal H}=
(G_{1}\Box H_{1},\ldots, G_{n}\Box H_{n},\ldots )$.
The sequence
$\mathcal{G\Box H}$\ is called the \emph{cartesian product }of\emph{\ }
$\mathcal{G}$\emph{\ }and\emph{\ }$\mathcal{H}$. The number of
vertices of the $n^{\emph{th}}$ element of $\mathcal{G\Box H}$ is
$N(G_{n}\Box H_{n})=N(G_{n})N(H_{n})$.
Here we are interested in the following probabilistic version of
Conjecture \ref{graham}.
\begin{conjecture}\label{hurlcon}
Let $\mathcal{F}$ and $\mathcal{G}$ be two graph
sequences with numbers of vertices $R=N(F_n)$ and $S=N(G_n)$, respectively,
and with pebbling thresholds $\tau_{\mathcal F}$ and $\tau_{\mathcal G}$,
respectively.
Let $f\in\tau_{\mathcal F}$, $g\in\tau_{\mathcal G}$, and
$h\in\tau_{\mathcal H}$, where ${\mathcal H}={\mathcal F}\Box{\mathcal G}$,
having $T=N(H_n)=RS$ vertices.
Then
\begin{equation*}
h(T)\in O(f(R)g(S))\ .
\end{equation*}
\end{conjecture}

This conjecture is shown to hold for $d$-dimensional grids (products of
paths) in \cite{ch}.
We are going to verify Conjecture \ref{hurlcon} for the cartesian
product of
cliques $\mathcal{K}^{2}=\mathcal{K\Box K}=(K_{1}\Box K_{1},\ldots,
K_{n}\Box K_{n},\ldots ).$
If true, the pebbling threshold for the product of cliques should be
\begin{equation*}
\tau _{\mathcal{K}^{2}}\subseteq \Theta (\sqrt{N^{1/2}}\sqrt{N^{1/2}}
)=\Theta (\sqrt{N})\ ,
\end{equation*}
where $N$ is the number of vertices of $\mathcal{K}^{2},$ namely $N=n^{2}$.
This would improve Boyle's \cite{boyle} result that $\tau _{\mathcal{K}
^{2}}\subseteq O(N^{3/4})$ and give the exact result (recall the
lower bound for all sequences mentioned above).
Our main result is the following theorem.
\begin{theorem}
\label{thmk2}Let $\mathcal{K}^{2}$ be the sequence of the cartesian products
of cliques, with $N=N(K_{n}^{2})$. Then the pebbling threshold of
$\mathcal{K}^{2}$ is
\begin{equation*}
\tau _{\mathcal{K}^{2}}=\Theta (\sqrt{N})\ .
\end{equation*}
\end{theorem}
This theorem is perhaps surprising, considering that the graph $K_n^2$ is
fairly sparse.  It seems that the structure of the graph is what keeps its
threshold small.

\section{Cops and Robbers}

Let us consider a particular configuration of pebbles on the cartesian
product of cliques $K_{n}\Box K_{n}$. Note that this graph can be thought
of as a rectangular grid with each row and column a complete graph.
Therefore, to pebble to a specific root $r$ one needs to collect
two or more pebbles on any vertex that belongs to the \textit{row}
$r\Box K_{n}$ or to the \textit{column} $
K_{n}\Box r$ (see Figure
\ref{cliquebyclique}). This suggests the following interpretation of the
pebbling problem.  We partition the vertices of $
K_{n}^{2}$ into three
distinct sets: \textit{police}, or \textit{cops} ($\mathbf{P}$
), \textit{citizens}
($\mathbf{T}$) and \textit{robbers} ($\mathbf{R}$).  Vertices in
the set $\mathbf{P}$ are those with two or more pebbles on them, $
\mathbf{T}$ is the set of vertices with one pebble, and $\mathbf{R}$
is the remaining set of empty vertices.  (This approach is motivated by
a variety ``Cops and Robbers'' games, one of the more prevalent types of
games on graphs. More information on these types of games can be found,
for example, in \cite{adler, coprob2, copsandrobbers, seymour}.)

\begin{figure}[tbp]
\centering
\resizebox {8cm}{7cm}
{\includegraphics[0,0][281,249]{cliquebyclique.eps} }
\caption{Schematic Presentation of $K_{n}\Box K_{n}$.}
\label{cliquebyclique}
\end{figure}

In our case, the robber is immobile and cops can move only in certain
directions and their number may change during the game. If root $r$ is
chosen in $\mathbf{R}$ then for a pebbling configuration to be solvable it
is sufficient that there is at least one cop
on $r\Box K_{n}$ or $K_{n}\Box r$. Any citizen can become a cop
if it is possible to move at least one pebble to it from some other cop.
We say that vertex $u$ \textit{sees }$v$ if $u$ and $v$ are in the
same row or column of $K_{n}^{2}.$ Furthermore, we say that a robber $
r=v_{0} $ can be \textit{caught }if there is a sequence of citizens $
v_{1},\ldots ,v_{k-1}$ and a cop $c=v_{k}$ so that $v_{i}$ sees $v_{i+1}$
for $0\leqslant i<k.$ Then the pebbling configuration is $r$-solvable if a
vertex $r$ can be caught. For example, on Figure \ref{policepath} it is
possible to pebble from the vertex $c$ (cop) to the vertex $r$ (robber).

Any
pebbling configuration $C$ determines the \emph{citizen subgraph}
\textit{\ }$G_C$ of $K_{n}^{2}$ induced by the vertex set $
\mathbf{P\cup T.}$ The edge set of $G_C$ is determined by the
vertices that see each other. Any component of $G_C$
containing two or more cops we call a \emph{police component}\textit{. }
\begin{claim}
\label{claimpolicecomp} Any configuration whose citizen subgraph has a police
component is solvable.
\end{claim}
\begin{proof}
Let us consider a police component with vertices $v_{1},\ldots
,v_{k} $ such that $v_{1},v_{k}\in \mathbf{P},$ $v_{1},\ldots ,v_{k-1}\in
\mathbf{T} $ and $v_{i-1}$ sees $v_{i}$ for $1\leqslant i<k$. We now use the
following strategy.  Without loss of generality, we
assume that $v_{1}$ and $v_{2}$ are in the same row $v_{1}\Box K_{n}$.
Then we find vertex $
v_1^{\prime }$ which is the intersection of $K_{n}\Box r$ and $v_{1}\Box K_{n}$
and make $v_1^\prime$ a citizen by moving a pebble from $v_{1}$.
Now $r=v_0$ can be caught by $v_1^\prime, v_2,\ldots,v_k$.
$\hfill$
\end{proof}
Another sufficient condition for a pebbling configuration to be solvable is
the existence of a ``robocop'', a vertex with $4$ or more pebbles on it. In
that case any robber $r$ can be caught by sending two pebbles to either $
K_{n}\Box r$ or $r\Box K_{n}$, making a cop there and moving a pebble to $r$
from this new cop. In Section \ref{comps} we prove that the probability that
such a ``robocop'' exists tends to zero.
Hence, our goal is to
prove that almost every configuration of asymptotically more than $n$
pebbles on $K_{n}^{2}$ has a police component.

\begin{figure}[tbp]
\centering
\resizebox {8cm}{7cm}
{\includegraphics[0,0][330,311]{policepath.eps} }
\caption{Pebbling from ``Cop'' to ``Robber''.}
\label{policepath}
\end{figure}

The next argument transforms the original problem of the solvability of a
pebbling configuration on $K^{2}$ to connectedness properties of a related
bipartite multigraph $B_{n,n}^{\prime }$. First, we observe that $K_{n}^{2}$
is isomorphic to the line graph of the complete bipartite graph $K_{n,n}$.
Indeed, both vertex sets are isomorphic to $\{1,\ldots,n\}^2$, and both
edge sets are isomorphic to pairs from $\{1,\ldots,n\}^2$ that share a
coordinate.
Similarly we construct a bipartite graph $B_{n,n}$ whose line graph is
isomorphic to $G_C$. The bipartite multigraph $
B_{n,n}^{\prime }$ is constructed from $B_{n,n}$ by adding multiple edges
according to the multiplicity of pebbles on the vertices of $G_C$.
In other words, for every vertex $(u,v)\in G_C$ we place the edge
$uv\in B_{n,n}^{\prime }$ with multiplicity $C((u,v))$.

\section{\label{secmodeldesc}Model Descriptions}

In this section we describe three different models for random bipartite
graphs and multigraphs . We compare them and determine asymptotic
implications from one to another which we can apply then to the pebbling
threshold on the product of graphs. In particular, we will be interested in
the property of having a large component (which will be shown to be a
police component almost surely).

The first model (Model A) is an analogue of the probabilistic model for
random graphs. In model A edges between any two vertices in different parts
of $B_{n,n}$ are mutually independent and have the same probability $p$.
Computations are easiest in this model, in which all graphs are simple.
The probability space corresponding to model A we
denote by $\mathcal{B}_{n,p}$.

The second model (Model B) is an analogue of the
static model for random graphs. First, the set of all bipartite simple
graphs on $n$ by $n$ vertices is denoted $\mathcal{B}(n)$.
The set of graphs in $\mathcal{B}(n)$ with $M$ edges we denote by $\mathcal{B}
(n,M)$. \noindent This model consists of $|\mathcal{B}(n,M)|=\binom{N}{M}$
different graphs, where $N=n^{2}$. Clearly, $\mathcal{B}(n)=
\cup_{M=0}^N\mathcal{B}(n,M).$

Finally, we need a generalization of the second model for the case of
bipartite multigraphs (Model B$^{\prime }$). As it was defined in the
previous section, the edges of the line graph represent pebbles; therefore
we need a multiple edge model to reflect this situation. We denote by $
\mathcal{B}^{\prime }(n,m)$ the set of all bipartite multigraphs on $n$ by $n$
vertices with $m$ edges$.$ \noindent Model B$^{\prime }$ consists of
precisely $|\mathcal{B}^{\prime }(n,m)|=
\QATOPD\langle \rangle {N}{m}$ different graphs, where $N=n^2$.
Finally, we define $
\mathcal{B}^{\prime }(n)=\cup_{m=0}^\infty \mathcal{B}
^{\prime }(n,m).$

The multiple edge model for random graphs was considered in \cite{austin}.
It was shown that the differences between simple graphs and multigraphs are
negligible in most cases. Janson et al. \cite{birth} give a detailed
analysis of the multigraph model using an algebraic approach.
We are going to show that, for the right translation of parameters, certain
properties that hold in model A will transfer to hold in B, and then to
B$^\prime$ as well.

\section{Connections Between Models}

Models A and B are very closely related to each other, provided that $M$ is
about $pN$, which is the expected number of edges of a graph in $
\mathcal{B}_{n,p}$. In fact, these two models are asymptotically equivalent
to each other for any convex property. Call a family of multisets $\mathcal M$
\emph{increasing}\ if $A\subseteq B$\ and $A\in \mathcal{M}$ implies that $
B\in \mathcal{M}$, \emph{decreasing}\ if $
A\subseteq B$\ and $B\in \mathcal{M}$ implies that $A\in \mathcal{M}$.
A family which is
either increasing or decreasing is called \emph{monotone}. Finally, a family
$\mathcal{M}$ is \emph{convex}\ if $A\subseteq B\subseteq C$
and $A,C\in \mathcal{M}$ imply that $B\in \mathcal{M}$.
Also, given a property $S$ we shall say that \emph{almost every}
(\emph{a.e.}) graph in the probability space $\mathcal{M}$
has property $S$ if $\Pr [G\in \mathcal{M}:G$ has $\mathbf{S}]\rightarrow 1,$
as $n\rightarrow \infty .$

The equivalence of models A and B follows from the general equivalence of
the probabilistic and static models in random graphs, which was proven by
Bollob\'{a}s (see \cite{bollobasgraph,palmer}).  Here we state the result
for random bipartite graphs.
\begin{result}
\label{equivalence} Let $N=n^2$ and let $0<p=p(n)<1$ be such that
$pN\rightarrow \infty $
and $(1-p)N\rightarrow \infty $ as $n\rightarrow \infty ,$ and let $
\mathbf{S}$ be a property of graphs.
\begin{enumerate}
\item  Suppose that $\varepsilon >0$ is fixed and that a.e. graph in $
\mathcal{B}(n,M)$ has $\mathbf{S}$ whenever
\begin{equation*}
(1-\varepsilon )pN<m<(1+\varepsilon )pN\ .
\end{equation*}
Then a.e. graph in $\mathcal{B}_{n,p}$ has $\mathbf{S}$.
\item  If $\mathbf{S}$ is a convex property and a.e. graph in $\mathcal{B}
_{n,p}$ has $\mathbf{S}$, then a.e. graph in $\mathcal{B}(n,M)$ has $\mathbf{
S}$ for $M=\left\lfloor pN\right\rfloor $.
\end{enumerate}
\end{result}
Bollob\'{a}s' technique is on the boolean lattice applied to graphs, so we
can apply it to bipartite graphs equally well since we are still considering
the boolean algebra in models A and B.
Next we establish a relationship between models B and B$^\prime$.

The \emph{support} of multigraph $G\in
\mathcal{B}^{\prime }(n)$\ is the simple graph obtained by identifying the
parallel edges of $G$.\ We denote the support by $\Lambda _{G}$. Obviously, $
\Lambda _{G}\in \mathcal{B}(n)$. We call the number of edges in the support
the \emph{size} of the support of $G$, written $Z=Z_G= ||\Lambda _{G}||$.
(Here we use the notation $||\cdot ||$ because we are counting edges rather
than vertices.)
The set of all graphs $G\in \mathcal{B}^{\prime }(n,m)$\ with the
same support size $Z_{G}=s$\ we denote $\Lambda (n,m,k)$.

An equivalent setting for the last definition is to consider $m$ unlabeled
balls placed in $N$ distinct urns. Then for $N=n^{2}$ the set $\Lambda _{G}$
represent the set of non-empty urns and $\Lambda (n,m,s)$ is the set of \
distributions into exactly $s$ of $N$ urns. We need to find the average size
of the support in this model. The probability that $G$ has support of size $
s,$ for $0\leqslant s\leqslant m,$ is
\begin{equation*}
\begin{tabular}{lll}
$\Pr [Z_{G}=s]$ & $=$ & $\dfrac{\binom{N}{s}\QATOPD\langle
\rangle {s}{m-s}}{\QATOPD\langle \rangle {N}{m}}$ \\
&  &  \\
& $=$ & $\dfrac{\binom{N}{s}\binom{m-1}{m-s}}{\binom{N+m-1}{m}}$ \\
&  &  \\
& $=$ & $\dfrac{\binom{N}{s}\binom{(N+m-1)-N}{m-s}}{\binom{N+m-1}{m}}$\ .
\end{tabular}
\end{equation*}
\newline
The last expression means that the random variable $Z=Z_{G}$
follows the hypergeometric distribution $\mathbf{H}$ with parameters $
\mathbf{H}(N+m-1,N,m)$. The hypergeometric distribution $\mathbf{H}(L,k,l)$
describes the number of white balls in the sample of size $l$ chosen
randomly (without replacement) from an urn containing $L$ balls, of which $k$
are white and $L-k$ are black.
Direct computations give us the expected value and the variance of $
Z_{G}$. Indeed, the general formula for $\mathbf{E}[Z^{k}]$ is
\begin{equation}
\begin{tabular}{lll}
$\mathbf{E}[Z^{k}]$ & $=$ & $\overset{N}{\underset{s=0}{\sum }}s^{k}\Pr
[Z=s] $ \\
&  &  \\
& $=$ & $\overset{N}{\underset{s=0}{\sum }}
s^{k}\dfrac{\binom{N}{s}\binom{m-1}{m-s}}{\binom{N+m-1
}{m}}$ \\
&  &  \\
& $=$ & $\dfrac{Nm}{N+m-1}\overset{N}{\underset{s=0}{\sum }}
s^{k-1}\dfrac{\binom{N-1}{s-1}\binom{
m-1}{m-s}}{\binom{(N+m-1)-1}{m-1}}$ \\
&  &  \\
& $=$ & $\dfrac{Nm}{N+m-1}\overset{N-1}{\underset{r=0}{\sum }}
(r+1)^{k-1}\dfrac{\binom{N-1}{r}
\binom{m-1}{(m-1)-r}}{\binom{N+m-2}{m-1}}$ \\
&  &  \\
& $=$ & $\dfrac{Nm}{N+m-1}E((Y+1)^{k-1})$\ ,
\end{tabular}
\label{etok}
\end{equation}
where $Y$ is a hypergeometric random variable with parameters $\mathbf{H}
(N+m-2,N-1,m-1)$.

Setting $k=1$ in the last line of equation (\ref{etok}), we obtain
\begin{equation}
\mathbf{E}[Z_{G}]=\dfrac{Nm}{N+m-1}=mq\ ,
\label{expectedvalue}
\end{equation}
with $q=\dfrac{N}{N+m-1}$. The intuitive idea is that, for a large value of $
N$, the average support size is close to $m.$ If the number of edges $
m=m(n)\in o(N)$
then the value of $q$ is close to one. According to the second moment
method, if the variance of random variable $Z_{G}$ is relatively
small then the value of $Z_{G}$ almost always stays close to the
mean. Indeed, in equation (\ref{etok}) if $k=2$ then
\begin{equation*}
\mathbf{E}[Z^{2}]=\dfrac{Nm}{N+m-1}\mathbf{E}[Y+1]=\dfrac{Nm}{N+m-1}\left(
\dfrac{(N-1)(m-1)}{N+m-2}+1\right) .
\end{equation*}
Therefore, the variance is

\begin{equation}
\begin{tabular}{lll}
$\func{Var}[Z_{G}]$ & $=$ & $\mathbf{E}[Z^{2}]-(\mathbf{E}
[Z])^{2} $ \\
&  &  \\
& = & $\dfrac{Nm}{N+m-1}\left( \dfrac{(N-1)(m-1)}{N+m-2}+1-\dfrac{Nm}{N+m-1}
\right) $ \\
&  &  \\
& = & $mq\Big[ (N-1)(m-1)(N+m-1)+(N+m-2)(N+m-1)- $ \\
&  &  \\
& & \qquad $-Nm(N+m-2) \Big]\ \Big/\ (N+m-2)(N+m-1) $\\
&  &  \\
& = & $\dfrac{mq}{N+m-2}\left( \dfrac{Nm-N-m+1}{N+m-1}\right) $ \\
&  &  \\
& = & $\dfrac{mq}{N+m-2}(N-1)(1-q)\ .$ \\%
&  &  \\
\end{tabular}
\label{variance}
\end{equation}

For $m(n)\in o(N)$ we have from Equations (\ref{expectedvalue}) and (\ref
{variance}) that
\begin{equation*}
\dfrac{\func{Var}[Z]}{(\mathbf{E}[Z])^{2}}=\dfrac{N-1}{N+m-2}\left( \dfrac{
1-q}{mq}\right) \rightarrow 0\ ,
\end{equation*}
as $n\rightarrow \infty .$ Hence, $\func{Var}[Z_{G}]\in o((\mathbf{
E}[Z_{G}])^{2}).$

Janson et al. \cite{randomjanson} suggested the following notation to
measure more precisely the closeness of a random variable to its mean.
\begin{notation}
Let $\{X_{n}\}_{n=1}^{\infty }$ be a sequence of random variables and $
\{a_{n}\}_{n=1}^{\infty }$ a sequence of positive real numbers. We write
\begin{equation*}
X_{n}=o_{p}(a_{n})
\end{equation*}
if, for every $\varepsilon >0,$ almost always $|X_{n}|<\varepsilon a_{n}$ $(
$i.e. $\Pr [|X_{n}|<\varepsilon a_{n}]\rightarrow 1$ as $n\rightarrow \infty
).$
\end{notation}
This definition is analogous to $o(\cdot )$, but with probability involved.
\begin{lemma}\label{suppsize}
\label{suppism}Let $q=\dfrac{N}{N+m-1}$ and $m\in m(n)\subseteq o(N)$. Then
\begin{equation*}
Z_{G}=mq+o_{p}(mq)\ ,
\end{equation*}
for a.e. graph $G$ in $\mathcal{B}^{\prime }(n,m)$.
\end{lemma}
\begin{proof}
We are going to use the second moment method with the random
variable $Z=Z_{G}$. We have $\mathbf{E}[Z]=mq$ by Equation \ref
{expectedvalue} and, using Equation \ref{variance} and Chebyshev's inequality,
we obtain
\begin{equation*}
\Pr [|Z-mq|>\lambda ]\leqslant \dfrac{\sigma ^{2}}{\lambda ^{2}}=\dfrac{mq}{
\lambda ^{2}}\dfrac{N-1}{N+m-2}(1-q)\leqslant \dfrac{mq}{\lambda ^{2}}\
\rightarrow 0\
\end{equation*}
for $\lambda =\varepsilon mq$ since $mq\rightarrow\infty$.
$\hfill$
\end{proof}
Now we are ready to establish the relationship between models B and B$
^{\prime }$. The next theorem provides a criterion for any increasing
property that holds in $\mathcal{B}(n,M)$ to hold in $\mathcal{B}^{\prime
}(n,m)$ as well.
\begin{theorem}
\label{equiv} Let $\mathbf{S}$ be any increasing
property of graphs and $q=N/(N+m-1)$
for some $m\in o(N).$ Also, let $B_{\mathbf{S}}(n,M)\subseteq \mathcal{
B}(n,M)$ and $B_{\mathbf{S}}^{\prime }(n,m)\subseteq \mathcal{B}^{\prime
}(n,m)$ denote those bipartite graphs and bipartite multigraphs,
respectively, having property $\mathbf{S}$. If for every sequence $M=M(n)$
such that $M=mq+o_{p}(mq)$ we have $\Pr [B_{\mathbf{S}}(n,M)]\rightarrow 1,$
as $n\rightarrow \infty ,$ then also $\Pr [B_{\mathbf{S}}^{\prime
}(n,m)]\rightarrow 1,$ as $n\rightarrow \infty $.
\end{theorem}
\begin{proof}
We are going to prove that $\Pr [B_{\mathbf{\bar{S}}}^{\prime
}(n,m)]\rightarrow 0.$ Let us consider the set
\begin{equation*}
\mathbf{M}(\varepsilon )=\{M\text{ }|\text{ }|M-mq|\leqslant \varepsilon
mq\}\ ,
\end{equation*}
for some $\varepsilon >0.$ We assume in the hypothesis that for any $M\in
\mathbf{M}(\varepsilon )$ we have
\begin{equation}
\Pr [B_{\mathbf{S}}(n,M)]\rightarrow 1\ ,
\label{assum}
\end{equation}
whenever $n\rightarrow \infty .$ Then
\begin{equation*}
\begin{tabular}{lll}
$\Pr [B_{\mathbf{\bar{S}}}^{\prime }(n,m)]$ & $=$ & $\sum\limits_{M\notin
\mathbf{M}(\varepsilon )}\Pr [B_{\mathbf{\bar{S}}}^{\prime }(n,m)$ $|$ $
Z_{G}=M]\Pr [Z_{G}=M]$ \\
&  &  \\
& $+$ & $\sum\limits_{M\in \mathbf{M}(\varepsilon )}\Pr [B_{\mathbf{\bar{S}}
}^{\prime }(n,m)$ $|$ $Z_{G}=M]\Pr [Z_{G}=M]\ .$
\end{tabular}
\end{equation*}
The first sum in the last expression can be bounded from above by
\begin{equation*}
\sum\limits_{M\notin \mathbf{M}(\varepsilon )}\Pr [Z_{G}=M]\ =\ \Pr
[Z_{G}\notin M(\varepsilon )]\ ,
\end{equation*}
which tends to zero by Lemma \ref{suppism}.
For every graph $B\in \mathcal{B}(n,M)$ there are
$\QATOPD\langle \rangle {M}{m-M}$ multigraphs
$B^\prime\in \mathcal{B}^{\prime }(n,m)$ with $
\Lambda _{B^\prime}=B$.
Moreover, $\mathbf{S}$ is increasing.
Therefore we can give an upper bound for the second sum of
\begin{equation}

\begin{tabular}{lll}
$\sum\limits_{M\in \mathbf{M}(\varepsilon )}\Pr [B_{\mathbf{\bar{S}}
}^{\prime }(n,m)\ |\ Z_{B^\prime}=M]$ & $\leqslant$ &
$\sum\limits_{M\in \mathbf{M}
(\varepsilon )}\dfrac{\QATOPD\langle\rangle{M}{m-M}|B_{\mathbf{\bar{S}}}(n,M)|}
{\QATOPD\langle \rangle {N}{M}}$ \\
&  &  \\
& $=$ & $\sum\limits_{M\in \mathbf{M}(\varepsilon )}\dfrac{\QATOPD\langle
\rangle {M}{m-M}\binom{N}{m}}{\QATOPD\langle \rangle {N}{M}}\Pr [B_{\mathbf{
\bar{S}}}(n,M)]$ \\
&  &  \\
& $\leqslant $ & $\Pr [B_{\mathbf{\bar{S}}}(n,M^{\ast })]\sum\limits_{M\in
\mathbf{M}(\varepsilon )}\dfrac{\QATOPD\langle \rangle {M}{m-M}\binom{N}{m}}{
\QATOPD\langle \rangle {N}{M}}\ ,$
\end{tabular}
\label{secondterm}
\end{equation}

where $M^{\ast }$ is the element of $\mathbf{M}(\varepsilon )$ that
maximizes $\Pr [B_{\mathbf{\bar{S}}}(n,M)\mathbf{].}$ The sum in the last
expression is a partial sum of probabilities of a hypergeometric random
variable and, therefore, does not exceed 1. Hence, the last line in (\ref
{secondterm}) is bounded from above by $\Pr [B_{\mathbf{\bar{S}}}(n,M^{\ast
})]$, which goes to zero, as $n\rightarrow \infty $, by assumption (
\ref{assum}). Thus, $\Pr [B_{\mathbf{\bar{S}}}^{\prime }(n,m)]\rightarrow 0$
as $n\rightarrow \infty $, and the statement of the theorem follows.
$\hfill$
\end{proof}
The particular increasing property in which we are most interested is that
of containing a large component, of size proportional to $2n$.
We will show that such a connected component is almost surely a police
component.

\section{\label{comps} Large Components and Police Components}

We first note that, almost surely, all cops have only two edges.
Recall that $B^\prime\in\mathcal{B}^\prime (n,m)$ is chosen uniformly
at random,
where $m=\varpi n$ and $\varpi\rightarrow\infty$ arbitrarily slowly as
$n\rightarrow\infty$.
The probability that there exists a vertex with $k$ pebbles on it is at most
\begin{equation*}
\dfrac{n^{2}\QATOPD\langle \rangle {n^{2}}{\varpi n-k}}{
\QATOPD\langle \rangle {n^{2}}{\varpi n}}\thicksim n^{2}\left( \dfrac{\varpi
n}{n^{2}+\varpi n}\right) ^{k}\thicksim n^{2}\left( \dfrac{\varpi }{n}
\right) ^{k}.
\end{equation*}
For $k>2$ the last expression tends to zero as $n\rightarrow\infty$.

We use this fact to show that connected components of linear size have
many cops.
\begin{lemma}\label{copcomp}
Let $H$ be a connected component of size $\alpha 2n$ in
$B^\prime\in\mathcal{B}^\prime (n,m)$, where $m=\varpi n$.
Then almost surely $H$ is a police component.
\end{lemma}
\begin{proof}
Let $x=x(n)$ be the excess of edges in $B^{\prime },$ namely $
x(n)=||B^{\prime }||-||\Lambda _{B^{\prime }}||$.
Since almost surely all cops have exactly two edges, the number of cops
$s=s(n)$ in $B^\prime$ is almost always equal to the excess $x(n)$.
Using Lemma \ref{suppsize} (with $q=N/(N+m-1)$) we compute
$$x(n) \ \sim \ m - mq \ = \ \varpi n (1-q) \ \sim \ \varpi^2 $$
almost surely.
Given that there are $\varpi^2$ cops in $B^\prime$, an upper bound of the probability that
$H$ has at most one cop is

\begin{eqnarray*}
\dfrac{ \dbinom{qn-\alpha 2n}{\varpi^2}
+\alpha 2n\dbinom{qn-\alpha 2n}{\varpi^2-1} }{\dbinom{qn}{\varpi^2}}
& \lesssim &
\left(\dfrac{qn-\alpha 2n}{qn}\right)^{\varpi^2}
\left(1+\dfrac{2\alpha n\varpi^2}{qn-2\alpha n-\varpi^2}\right) \\
& & \\
& \lesssim &
e^{-2\alpha\varpi^2/q}
\left(\dfrac{2\alpha\varpi^2}{q-2\alpha-\varpi^2/n}\right)\ .
\end{eqnarray*}

We may assume that $H$ is small, so if $4\alpha<q$ the last term is
at most $\varpi^2 e^{-\varpi^2/2}\rightarrow 0$ as $n\rightarrow\infty$.
$\hfill$
\end{proof}
Finally, we prove that there is a connected component of linear size in
$\mathcal{B}_{n,p}$.  The following theorem was proven in \cite{delavega}
for the random graph $\mathcal{G}_{n,p}$.  The proof involved analyzing
the hitting time of a certain parameter in a random walk and used no
special property of the graph structure.  Here we modify the result for
the random bipartite graph $\mathcal{B}_{n,p}$.  The same method yields
the following result, which we state without proof.
\begin{result}\label{dlv}
Let $\beta>\ln 16$, $p=\beta/n$, and $B_n\in\mathcal{B}_{n,p}$.
Then almost surely there is a path in $B_n$ of length at least
$(1-(\ln 16)/\beta)2n$.
\end{result}

\section{\label{secthrk2} Proof of Theorem \ref{thmk2}}

Now we prove that $\tau_{\mathcal{K}^2}=\Theta(\sqrt{N})$.
\begin{proof}
We recall that the pebbling threshold of every graph sequence is in
$\Omega(\sqrt{N})$.  Therefore we need only show that
$\tau_{\mathcal{K}^2}=O(\sqrt{N})$.  Write $N=n^2$, let $m=\varpi n$, where
$\varpi=\varpi(n)\rightarrow\infty$ arbitrarily slowly, and let $C$ be a
randomly chosen configuration from $\mathbf{C}_{N,m}$.
Let $B^\prime_{n,n}\in \mathcal{B}^\prime (n,m)$ be the bipartite
multigraph associated with $C$, and $B_{n,n}\in \mathcal{B}(n,M)$
be the simple bipartite graph determined by the support of $B^\prime_{n,n}$.
Lemma \ref{suppsize} implies $M=mq+o_p(mq)$, where $q=M/(M+n-1)$.

Let $p=M/N$ and consider the probability space $\mathcal{B}_{n,p}$.
For a graph $G$ let $\mathbf{S}=\mathcal{S}(G)$ be the property that $G$
has a connected component of size at least $\alpha |G|$, where
$\alpha=q/4$.  Define $\beta >\ln 16$ by $\alpha=1-(\ln 16)/\beta$ and let
$p^\prime=\beta/n$.  Then Result \ref{dlv} implies that almost every
graph in $\mathcal{B}_{n,p^\prime}$ has $\mathbf{S}$.  Since almost surely
$p\sim mq/N\sim (\varpi/n)e^{-\varpi/n} > p^\prime$, and $\mathbf{S}$ is
an increasing property, almost every graph in $\mathcal{B}_{n,p}$ has
$\mathbf{S}$.
Every increasing property is also convex.  Thus Theorem
\ref{equivalence} assures that almost every graph in $\mathcal{B}(n,M)$
has $\mathbf{S}$.  Then Theorem \ref{equiv} implies that almost every
graph in $\mathcal{B}^\prime (n,m)$ has $\mathbf{S}$.  Let $H$ be such
a connected component of $B^\prime_{n,n}$ of size at least $\alpha 2n$.
According to Lemma \ref{copcomp} $H$ is almost surely a police component.
Finally, let $H_C$ be the corresponding connected component of the
citizen subgraph $G_C$ of the configuration $C$.  Since $H_C$ is a police
component, Claim \ref{claimpolicecomp} implies that $C$ is solvable.
This finishes the proof.
$\hfill$
\end{proof}

\section{Future Research}

Consider the graph $K_n^d=K_n^{d-1}\Box K_n$, and the sequence
$\mathcal{K}^d=\{K_1^d,\ldots,K_n^d,\ldots\}$.
If Conjecture \ref{hurlcon} is true then induction would show that
$\tau_{\mathcal{K}^d}=\Theta(\sqrt{N})$ for all $d$.  On the surface
such a result might be surprising, considering the sparcity of the graphs
(size $n^d$, degree $d(n-1)$).  However, its low diameter and high
structure make such a result believable.

Another interesting test for Conjecture \ref{hurlcon} is the sequence
of $n$-dimensional cubes $\mathcal{Q} =\{Q^1,\ldots,Q^n,\ldots\}$, where
$Q^n=Q^{n-1}\Box Q^1$, and $Q^1$ is the path on two vertices.  Because
$\mathcal{Q}^2$ is a subsequence of $\mathcal{Q}$, we must have
$\tau_{\mathcal{Q}^2}=\tau_\mathcal{Q}$.  Therefore, if $\tau_\mathcal{Q}
=\Theta(N^\alpha f(N))$ for some function $f(N)$, one can see that $f(N)$
must submultiplicative; i.e. $f(xy)\leqslant f(x)f(y)$ must hold.
The best result
to date is that $\tau_\mathcal{Q}\in \Omega(N^{1-\epsilon})\cap O(N/\lg N)$
for all $\epsilon>0$ (see \cite{cw}).

\section*{Acknowledgments}

The authors wish to thank Graham Brightwell for useful hallway conversations
during his visit to ASU.