PROOF SAMPLE

M. J. KLEIN

Date: November 21, 2017.

1. Introduction

This problem came up in the process of searching for lower bounds on the number of cycles in a graph with certain properties.

I chose this proof as my sample because it’s my favorite short proof. The final bit of reasoning is analogous to reducing the problem to a halting problem and solving that halting problem.

2. Proof

This is a proof of the lower bound of the pseudo-boolean function

( ) m∑ -1 ∑i 2 f(A ) := aj i=1 j=1
given that A ∈ Bm-1, ε = ∑ i=1m-1a i = constant, and m ≥ 2. In other words, this is an optimization of the function f : Bm-1 → ℤ, where the binary input vector has a given Hamming Weight.

Lemma 2.1.

m∑ -1∑ i m∑ -1 m∑-1 aj = m ai - iai i=1 j=1 i=1 i=1

Proof.

m∑ -1∑i aj = (a1) + (a1 + a2) + (a1 + a2 + a3) + ... i=1 j=1
We have (m - i) copies of ai so
m -1 i m- 1 m- 1 m -1 ∑ ∑ ∑ ∑ ∑ aj = (m - i)ai = m ai - iai i=1 j=1 i=1 i=1 i=1
□

Lemma 2.2.

m-1 i m-1 m- 1 m -1 m-1 ∑ ∑ m2- ∑ m- ∑ 1∑ 1-∑ 2 aji = 2 ai - 2 ai + 2 iai - 2 i ai i=1 j=1 i=1 i=1 i=1 i=1

Proof.

∑ i=1m-1 ∑ j=1ia ji = 1(a1) + 2(a1 + a2) + 3(a1 + a2 + a3) + …
= a1 ∑ j=1m-1j + a 2 ∑ j=2m-1j + a 3 ∑ j=3m-1j + …
But ∑ j=im-1j = (m - i)(m + i - 1)∕2 so then we have:
∑ i=1m-1 ∑ j=1ia ji = ∑ i=1m-1a i(m - i)(m + i - 1)∕2
= 1- 2 ∑ i=1m-1a i(m2 - m + i - i2)
= m2 --- 2 ∑ i=1m-1a i -m -- 2 ∑ i=1m-1a i + 1 -- 2 ∑ i=1m-1ia i -1 -- 2 ∑ i=1m-1i2a i
□

Lemma 2.3.

( )2 ( ) ∑m ∑i ∑m ∑m i-∑ 1 am+1-j = iai + 2jajai i=1 j=1 i=1 i=2 j=1

Proof. Note that

( ) ∑i 2 ∑i ∑i am+1- j = a2m+1- j + 2 am+1-jam+1 -k j=1 j=1 j<k
But am+1-j2 = a m+1-j, because am+1-j ∈{0, 1} so:
∑ i ∑i a2 = a m+1 -j m+1-j j=1 j=1
Thus
m ( i )2 m ( i ) m ( i ) ∑ ∑ ∑ ∑ ∑ ∑ am+1 -j = am+1 -j + 2 am+1 -jam+1- k i=1 j=1 i=1 j=1 i=1 j<k
But note that, because there are i copies of am+1-(m+1-i),
( ) ∑m ∑ i ∑m am+1- j = iai i=1 j=1 i=1
Likewise, there are i copies of each distinct pair of a’s, so
∑m ( ∑i ) ∑m ( i∑-1 ) 2 a a = 2ja a m+1- j m+1-k j i i=1 j<k i=1 j=2
□

Theorem 1.

( )2 1 m∑ -1 ∑i --ε(ε + 1)(2 ε + 1) ≤ aj = f (A) 6 i=1 j=1

Proof. We begin by reversing the indices of the aj’s and applying Lemma 2.3 to get

m∑-1( ∑ i )2 ∑m ∑m ( ∑i-1 ) a = ia + 2ja a j i j i i=1 j=1 i=1 i=2 j=1
Recall that ε = ∑ i=1m-1a i. We first consider the trivial cases of ε = 0, 1.

If ε = 0, then all the ai = 0 and so the total is 0 and the theorem holds.

If ε = 1, then exactly one ai≠0. Let us call it ap for positive. Then the total is equal to kak, because no pair of ai’s can be non-zero. Taking the minimum k = 1, we get the total is 1 and the theorem holds.

Note that if az is positive, it adds exactly z + 2z ∑ j=z+1ma j to the total, independent of the rest.

Suppose that there exists some y such that ay = 1 and for all ai = 0, i < y. Let y be the minimum such index. The contribution of ay is y + 2y ∑ j=y+1ma j. Similarly the contribution of ay-1, if we swap the values of ay and ay-1, is (y - 1) + 2(y - 1) ∑ j=yma j. However, if we only swap these two values, the values, and thus the contributions of those values, with index greater than y are left unchanged. Therefore, the contribution of ay-1, if the values are swapped, is

∑m (y - 1) + 2(y - 1) aj. j=y+1
As this operation of swapping the first positive value above all the zero-values will always decrease the total, one may repeat this operation as long as there are positive values with higher index than some zero value. Therefore, the minimum total is exactly the assignment where there is no non-positive assignment below a positive one, that is precisely the assignment with all positive assignments at the lowest possible indices.

Thus our minimum total, given that ε < i implies that ai = 0, is

( ) ∑ε ∑ε ∑i- 1 1 i + 2jajai = -ε (ε + 1)(2ε + 1). i=1 i=2 j=1 6
□