A Portion of the Book

July 27, 2009

Chevalley-Warning and Combinatorics

Filed under: Combinatorics, Number Theory — by Masoud Zargar @ 2:29 pm

Recently, I have been studying the two theorems that are of importance to zero-sum theory: Combinatorial Nullstellensatz and the Chevalley-Warning Theorem. The former method of proof is also referred to as the Noga Alon polynomial method. You may read Combinatorial Nullstellensatz, a very interesting paper attributed to Noga Alon. That being said, I would like to discuss the latter theorem along with several of its applications in combinatorics. The Chevalley-Warning Theorem is concerned with the solutions to a system of polynomial equations over finite fields. As far as combinatorial problems are concerned, the construction of this system is crucial. Usually, when working over $\mathbb{F}_p$ , the Chevalley-Warning theorem coupled with Fermat’s Little Theorem form the basis for the construction of the system.

Zero-sum problems comprise a class of combinatorial problems that are of the form: given a finite abelian group $G$ and an integer $n$ , find the smallest integer $k$ such that among any sequence of $k$ elements of $G$ , there are $n$ of them that sum to $0$ . For example, we obtain the Erdős-Ginzburg-Ziv theorem when $G:=\mathbb{Z}\slash n\mathbb{Z}$ , i.e. among any $2n-1$ integers, you can find exactly $n$ of them whose sum is divisible by $n$ .

After an elementary proof of the Chevalley-Warning theorem has been provided, a proof of the Erdős-Ginzburg-Ziv will be given. Then a graph theoretic problem followed by a lemma of Alon and Dubiner (a crucial step in C. Reiher’s proof of Kemnitz’s conjecture in 2003) will be in order. (more…)

Comments (6)

July 19, 2009

Cauchy’s Method of Induction

Filed under: Miscellaneous — by Masoud Zargar @ 6:47 pm

Being in the course of writing a couple of blog entries on a couple of technical topics, in the meantime, I would like to discuss a method of induction that is believed to have originated from Cauchy’s works. I will illustrate the method by proving a couple of inequalities. Initially, I will discuss a proof of the Arithmetic-Geometric Means inequality followed by a proof of a nice inequality.

For those readers who are unaware of the Arithmetic-Geometric Means inequality:

(Arithmetic-Geometric Means Inequality) If $a_1,\hdots,a_n\geq 0$ are real numbers, then $\displaystyle \frac{1}{n}\sum_ia_i\geq\sqrt[n]{\prod_{i}a_i }$ .

Let’s demonstrate Cauchy’s method of induction by proving this ubiquitous inequality. (more…)

Comments (4)

July 9, 2009

Invariants

Filed under: Combinatorics — by Masoud Zargar @ 11:52 pm

Problem 2. You are given markers each being one of the three colors green, blue, and red. A

step is composed of taking two markers of dierent colors and replacing them with a marker of the

third color. Prove that the color of the last marker remaining either does not depend on the way

you perform the steps or could be any of the three colors.

When I was in high school (last year), I wrote about 50 pages (two chapters) on a wide range of topics in number theory and combinatorics. Each chapter was divided into short sections on independent topics followed by a collection of problems with their solutions. The first section was on the invariance principal. Here, I have reproduced that section for this blog; however, I have refrained from posting the solutions in order to eliminate some temptations to look at the solutions.

***

The invariance principle says that if there is change, look for the properties that does not change, i.e. look for the invariants.

This principle can sometimes be used to solve problems that involve a fixed set of legal moves. Consider the following problem as an example.

Given three numbers $a,b,c$ on a blackboard, a step is composed of taking any of the three numbers and adding to it the difference of the other two numbers multiplied by any rational numbers. For example, you can map $(a,b,c)\mapsto \left( a+|b-c|\frac{p}{q},b,c\right)$ , where $\frac{p}{q}\in\mathbb{Q}$ . Can you obtain the set $\{0,2,\sqrt{3}\}$ starting with $\{0,1,\sqrt{3}\}$ ?

At first sight, this problem may seem very diffcult. If you notice that when you perform a step, $(a,b,c)\mapsto \left( a+|b-c|\frac{p}{q},b,c\right)$ , you are in fact translating a point by vector, then you may think of a geometric interpretation of this problem.

So what can we do? Let’s find a property that remains invariant.

(more…)

Comments (2)

June 8, 2009

A Word on p+22

Filed under: Number Theory — by Masoud Zargar @ 12:12 am

There is a class of conjectures that deal with the integral solutions $(p,n)$ to $p=f(n)$ , where $p$ is a prime and $f\in\mathbb{Z}[x]$ with $\deg f=2$ . For example, it is open whether or not the above equation has an infinite number of solutions when $f(X)=X^2+1$ . In this entry, I would like to discuss the solutions to $p+22=n^2$ , where $p$ is a prime and $n\in\mathbb{Z}$ . Notice that this is easier to approach than finding all prime numbers of the form $n^2+1$ due to the fact that one can discuss quadratic residues modulo $11$ or $22$ for the former equation, whereas the latter equation is not susceptible to such approaches at first sight. I claim the following:

Theorem. If $p$ is a prime of the form $n^2-22$ , then if $p\neq 3$ , then $p\equiv\{59,131\}\pmod{144}$ .

Proof. Equivalently, we have to prove that if $p+22$ is a perfect square, then $p\equiv\{59,131\}\pmod{144}$ , hence the name of the entry. Notice that $p=3$ satifies $3+22=5^2$ , so $3$ is of the desired form. Suppose now that $p\neq 3$ . Notice that $0,1$ are the only squares $\bmod 3$ . Assume that $3\nmid n$ . Then it follows that

$p+1\equiv p+22\equiv n^2\equiv 1\pmod 3\implies 3|p\implies p=3$ ,

a contradiction to our assumption. So $3|n$ . Therefore, $9|n^2$ , and $p+4\equiv p+22\equiv 0\pmod{9}\implies p\equiv 5\pmod{9}$ .

Niether $2$ nor $11$ are primes of the desired form, so $(p,22)=1$ . Modulo $p$ , $22$ is a quadratic residue, so by the Quadratic Reciprocity law,

$1=\left(\frac{22}{p}\right)=\left(\frac{2}{p}\right)\left(\frac{11}{p}\right)=(-1)^{\frac{p^2-1}{8}}\left(\frac{p}{11}\right)(-1)^{\frac{(p-1)(11-1)}{4}}$

Since modulo $11$ , $p\equiv n^2\pmod{11}$ , $\left(\frac{p}{11}\right)=1$ . Ergo, $1=(-1)^{\frac{p^2-1}{8}+\frac{p-1}{2}}$ . So we want to have $2|\frac{p^2+4p-5}{8}$ , i.e. $(p+2)^2-9\equiv p^2+4p-5\equiv 0\pmod{16}$ . A simple calculation gives that only $x\equiv 3,5,11,13\pmod{16}$ satisfy $x^2\equiv 9\pmod{16}$ . Cosequently, $p\equiv 1,3,9,11\pmod{16}$ . But not all of these satisfy our needs. Since $p\neq 2$ ( $2+22=24$ is not a perfect square), $p+22=n^2$ must be an odd square. So modulo $8$ ,

$p-2\equiv p+22\equiv n^2\equiv 1\pmod{8}\implies p\equiv 3\pmod 8$ .

Thus, only $p\equiv 3,11\pmod{16}$ are possible. The rest is a simple result of the Chinese Remainder Theorem given

$\begin{cases}p\equiv 5\pmod 9\\ p\equiv 3\pmod{16}\end{cases}$

$\begin{cases}p\equiv 5\pmod{9}\\ p\equiv 11\pmod{16}\end{cases}$ .

These lead to $p\equiv\{59,131\}\pmod{144}$ , as required. $\Box$

This approach may certainly be extended to more general results, but I will leave the investigation to the reader for now. Any new insight regarding primes of the form $n^2-22$ is certainly welcome.

June 7, 2009

The Fundamental Theorem of Algebra I

Filed under: Complex Analysis — by Masoud Zargar @ 6:43 pm

As a result of the very beautiful mathematics out there, it has been very difficult to keep my word about regularly posting here. I have been procrastinating to complete the last post on Fourier series and its applications (Fourier Series, Geometry, and Summation) for I would like to continue it with a discussion of infinite pre-Hilbert spaces and their applications. In this post, however, I would like to include two proofs of the Fundamental Theorem of Algebra, i.e. $\mathbb{C}$ is algebraically closed.

There are many proofs of the Fundamental Theorem of Algebra, but there are two that I particularly like because of their elegance and the way they seem to be far from intuition at first sight: a topological proof and another using complex analysis. Trying to make this post self contained, brief proofs of the results used will be given. Furthermore, for motivational purposes, non-related applications, e.g. the Borsuk-Ulam and the Brouwer Fixed Point theorems in two dimensions, of the proved results will be given.

A formal stating the fundamental theorem of algebra:

Every nonconstant $f\in\mathbb{C}[z]$ has a root in $\mathbb{C}$

Notice that this implies the following ubiquitous theorem (also known as the fundamental theorem of algebra) that many take for granted:

Every polynomial $f(z)=a_nz^n+\hdots+a_0$ with $\deg f=n\geq 1$ has precisely $n$ roots. If these roots are $z_1,\hdots,z_n$ (not necessarily distinct), then $f(z)=a_n(z-z_1)\hdots(z-z_n)$ .

You may be wondering how this latter result follows from the former.

The former result states that $f$ has a roots, say $z_1$ . Then $f(z)=f((z-z_1)+z_1)=\sum_{k=0}^na_k((z-z_1)+z_1)^k$ . By Newton’s Binomial Theorem, expanding $((z-z_1)+z_1)^k$ for all $k$ results in $f(z)=b_n(z-z_1)^n+\hdots+b_1(z-z_1)+b_0$ . Since $b_0=f(z_1)=0$ , we have $f(z)=(z-z_1)g(z)$ , $\deg g=n-1$ . By induction on the degree of polynomials in $\mathbb{C}[z]$ , the result follows.

(more…)

Comments (1)

May 21, 2009

Fourier Series, Geometry, and Summation

Filed under: Fourier Analysis — by Masoud Zargar @ 8:27 am

Clearly, the analytic representation of functions is a very important topic in mathematics, and it has been proved worthwhile to develop this part of mathematics. Nearly fifty years had passed until Fourier became pregnant with ideas that shed new light on Fourier series, which developed into a whole branch called Fourier Analysis. In this post, I will try to motivate the study of Fourier series and discuss simple, yet extremely useful, that will allow us to solve some nice Olympiad and standard summation problems. It is worthwhile to try to motivate the study of this subject.

It is not only true that theorems in Fourier Analysis improve our arsenal of mathematical methods, but the sole introduction of the notations allows us to think of some difficult problems as though they are trivial. For example, consider the following variant of Marius Cavachi’s problem of the Romanian Mathematical Olympiad:

Suppose that there are $n$ points $P_1,\hdots,P_n$ in the plane. Prove that there is a point $P$ on $S^1$ such that $\prod_{i=1}^n|\overrightarrow{PP_i}|\geq 1$ .

A question to consider: What can we do when we are given a finite set $S=\{P_1,\hdots,P_n\}$ of point in the plane and are told to consider the product of the distances of the points from a fixed point $P\notin S$ ?

A suitable way to proceed is to consider $\mathbb{C}$ instead of $\mathbb{R}^2$ and represent our points as complex numbers. This transformation is done in order to make use of the field and analytic structures of $\mathbb{C}$ . So, let us restate the above problem in the following way:

Given a set of complex numbers $z_1,\hdots,z_n$ , prove that there is a point $z\in S^1=\{z\in\mathbb{C}: |z|=1\}$ such that $\prod_{i=1}^n|z-z_i|\geq 1$ .

(more…)

Comments (6)

May 11, 2009

Germs and Derivations

Filed under: Differential Forms — by Masoud Zargar @ 12:05 pm

Having started to study manifolds during the summer, I think that it is suitable to write about what I have learned to improve my understanding of the subject. One could try to describe tangent spaces at a point $p$ on a surface by definding it as the vector space of all tangent vectors to the surface at the point $p$ ; intuitively, this is the tangent plane to the surface at the point $p$ . However, this idea strictly works in spaces that are embedded in the Euclidean space, and so it would be difficult to describe such a creature on, say, a projective plane which is not a subset of $\mathbb{R}^n$ . To be able to generalize this idea, which is of utmost importance in the theory of manifolds, we must modify this definition so that it will easily generalize to abstract manifolds. As in any book on differential topology/manifolds, we need to develop many definitions before we could say anything of substantial importance and beauty on this subject.

Tangent Space

We define the set $T_p\mathbb{R}^n$ as the vector space of all vectors with tail at the point $p$ ; it is more or less a shift of the origin in $\mathbb{R}^n$ to the point $p$ . Notice that $T_p\mathbb{R}^n\simeq \mathbb{R}^n$ (vector space isomorphism). We let ${e^1,\hdots,e^n}$ and ${e_p^1,\hdots,e_p^n}$ be the standard bases for $\mathbb{R}^n$ and $T_p\mathbb{R}^n$ , respectively. (more…)

April 8, 2009

Integrals, Combinatorics, and Geometry

Filed under: Combinatorics — by Masoud Zargar @ 9:27 am

Clearly, integrals are of profound importance and interest to most, if not all, mathematicians. A topic that is rarely incorporated into the required mathematics courses, let it be at the undergraduate or graduate level, is the applications of integrals to combinatorics, especially those combinatorial questions that do not have an algebraic flavour.

In this article, several interesting and useful ideas concerning geometric combinatorics and combinatorial identities will be introduced. The geometric combinatorics discussion will primarily deal with a very powerful technique that uses integrals of characteristic functions. Here, we will deal with Lebesgue integrals, and so $\int_{C}1$ is simply the planar measure of measurable $C$ ; our sets $C$ will be sufficiently nice, and so if you are unaware of the terminology used in Lebesgue integration, you can think of $\int_C1$ as the area of $C$ . As I strongly believe that mathematics should be taught via examples and problems, as in An Important Equivalence Relation the ideas will be introduced by discussing several problems. Initially, a technical solution will be given to a combinatorial geometry problem that has a simple elementary solution; however, the power of the method will be demonstrated by claiming that a more general relation holds that could be nontrvial depending on the parameters. The story will certainly not end here! A solution will be given to a combinatorial (geometry) problem using trigonometric functions, followed by the solution to a combinatorial identity by rewriting the terms under consideration in terms of integrals. Digressing, integrals will be used to show the power of averagin using integral (even in combiantorial problems with a geometric flavour). This entry will then end with a discussion of a beautiful solution to Putnam 2005 B6. Following this plan, consider the following problem in extremal combinatorial geometry:

Suppose that you have nine planar surfaces $S_1,\hdots,S_9$ each of area $1$ , whose union is a surface of a surface of area $5$ . Prove that there are $i\neq j$ such that $S_i\cap S_j$ has area at least $\frac{1}{9}$ .

You can give a short proof to this by assuming the contrary (why?), but that is a different story that may be pursued in the near future. For the purpose of making sure that we are all on the same page, given a set $S\subseteq T$ , the characteristic function $\chi_S:T\rightarrow\{0,1\}$ of $S$ in $T$ is defined as

$\chi_S(x) =\begin{cases}0, x\notin S;\\ 1, x\in S.\end{cases}$

Now, here is the solution to the above problem:

Solution.Consider the function $f:S=\cup_iS_i\rightarrow\mathbb{Z}$ given by $f=\sum_i\chi_{S_i}$ . Then $f$ takes integer values, so $(f-1)(f-2)\geq 0$ . Therefore,

$0 \leq\int_Sf^2-3\int_Sf+\int_S2= -2\sum_i\int_S\chi_{S_i}+2\sum_{i<j}\int_S\chi_{S_i\cap S_j}+10$

Because $\int_S\chi_{S_i}=\int_{S_i}1=1 \forall i\in[9]$ , we have $\sum_{i<j}\int_{S}\chi_{S_i\cap S_j}\geq 4$ . The left hand side has $\binom{9}{2}=36$ summands, and so there must be $i\neq j$ such that $\int_{S_i\cap S_j}1=\int_S\chi_{S_i\cap S_j}\geq\frac{1}{9}$ ; otherwise, the left hand side is less than $\frac{1}{9}\binom{9}{2}=4$ . $\Box$

(more…)

Comments (1)

March 26, 2009

An Important Equivalence Relation

Filed under: Group Theory — by Masoud Zargar @ 6:57 am

There exists an important equivalence relation that is fundamental to group theory, and useful in number theory and combinatorics; in fact, this equivalence relation could be thought of as a problem solving method to look for when you are to prove a property closely related to divisibility in a set.

An equivalence relation $\sim$ on a set $S$ partitions $S$ into equivalence classes $[x]=\{ y\in S|x\sim y\}$ which is a consequence of satisfying the following properties:

$x\sim x\ \forall x\in S$
$x\sim y\iff y\sim x\ \forall x,y\in S$
$x\sim y, y\sim z\implies x\sim z\ \forall x,y,z\in S$

These properties are called reflexivity, symmetry, and transitivity, respectively. It is a nice, albeit elementary, exercise to prove that any equivalence relation on any set $S$ defines a partition on $S$ .

The method of proof that is going to be discussed in this article is going to be illustarated by giving an elegant combinatorial proof of Fermat’s Little Theory, reproducing McKay’s proof of Cauchy’s Group theorem, and solving problem A5 of Putnam 2007 along with asking for a proof of its generalization appearing as AMM Problem 10775.

Fermat’s Little Theorem was presumably proved by Fermat, but the first known proof was given by Euler in 1749.

Fermat’s Little Theorem (1749): Given a prime $p$ and $a\in\mathbb{Z}$ , $a^p\equiv a\pmod p$ .

This theorem is, in fact, a special case of Euler’s Totient Formula, which in in turn a special case of Lagrange’s Group Theorem applied to the group $(\mathbb{Z}\slash m\mathbb{Z})^{\times}$ . There are also non group theoretic proofs using induction and the fact that $\phi:(\mathbb{Z}\slash m\mathbb{Z})^{\times}\rightarrow (\mathbb{Z}\slash m\mathbb{Z})^{\times}$ given by $x\mapsto ax$ is a bijection. These proofs, albeit elegant, are different stories. The following is the story of our interest in this article:

Proof. Suppose that were have $p$ -tuples, each of whose entries come from a set of cardinality $a$ . So there are $a^p$ such $p$ -tuples. (more…)

Comments (4)

A Portion of the Book

July 27, 2009

Chevalley-Warning and Combinatorics

July 19, 2009

Cauchy’s Method of Induction

July 9, 2009

Invariants

June 8, 2009

A Word on p+22

June 7, 2009

The Fundamental Theorem of Algebra I

May 21, 2009

Fourier Series, Geometry, and Summation

May 11, 2009

Germs and Derivations

Tangent Space

April 8, 2009

Integrals, Combinatorics, and Geometry

March 26, 2009

An Important Equivalence Relation

Pages

Recent Posts

Categories

Blogroll

Weblogs

Archives

Meta