This post follows a recent paper On sunflowers  and matrix multiplication by Noga Alon, Amir Spilka, and Christopher Umens (ASU11) which rely on an earlier paper Group-theoretic algorithms for matrix multiplication, by Henry Cohn, Robert Kleinberg, Balasz Szegedy, and Christopher Umans (CKSU05), and refers also to a paper by Don Coppersmith and Shmuel Winograd (CW90). 

Three famous problems
The Erdos-Rado sunflower conjecture
The Erdos-Rado sunflower (Delta system) theorem and conjecture was already menioned in this post on extremal set theory.

A sunflower (a.k.a. Delta-system) of size is a family of sets such that every element that belongs to more than oneofthe sets belongs to all of them. A basic and simple result of Erdos and Rado asserts that

Erdos-Rado sunflower theorem: There is a function so that every family of -sets with more than  members contains a sunflower of size .

One of the most famous open problems in extremal combinatorics is:

The Erdos-Rado conjecture: Prove that .

Here, is a constant depending on . This is most interesting already for .

Three term arithmetic progressions
The cup set problem (three terms arithmetic progressions in ):

The cup set problem was also discussed here quite extensively. (See, e.g. this post.)

Let . The cap set problem  asks for the maximum number of elements in a subset of  which contains no arithmetic progression of size three or, alternatively, no three vectors that sum up to 0(modulo 3). (Such a set is called a cup set.) If is a cap set of maximum size we can ask how the function behaves. Roy Meshulam proved, using Roth’s argument, that . Edell found an example of a cap set of size . So .  The gap is exponential.  

The strong cap set conjecture: for some .

Of course, the cap set problem is closely related to

Erdos-Turan problem (for ): What is the larget size  of a subest of {1,2,…,n} without 3-term arithmetic progression?

Matrix multiplications
Let ω be the smallest real number so that there is an algorithm for multiplying  two matrices which requires arithmetic operations.  

The ω=2 conjecture: ω=2.

A very recent breakthrough by Virginia Vassilevska Williams (independently) following an earlier breakthrough by Andrew Stothers improved the Coppersmith-Winograd algorithm which gave ω =2.376, to 2.374 and 2.373 respectively. (See the discussions over Lipton’s blog (1,2), Shtetl optimized, and Computational Complexity.)

It turns out that these three conjectures are related. (The connection of matrix multiplication and the Erdos-Turan problem is fairly old, but I am not sure what an even drastic improvment of Behrends’s lower bound would say about .)

Three combinatorial conjectures that imply ω=2.
Remarkably, an affarmative answer for the ω=2 conjecture would folow from each one of three combinatorial conjectures. One conjecture goes back to CW90 and two were described in CKSU05. I will not present the precise formulations in order to encourage the readers to look at the original papers. (Maybe I will add the formulations later.)

The no disjoint equivoluminous subsets conjecture (CW90).

The Strong UPS conjecture (CKSU05).

Theorem: Conjecture CW90 implies the strong UPS conjecture.

CKSU’s two-family conjecture (CKSU05).

Relations between these problems
Here are some results taken from ASU11 about the relations between these combinatorial questions. The first result goes back to Erdos and Szemeredi.

The weak sunflower conjecture: A family of subsets of {1,2,…,n}  with no sunflower of size 3 can have at most sets.

The following results are not difficult.

Theorem: The strong sunflower conjecture implies the weak sunflower conjecture.

Theorem: The strong cup set conjecture also implies the weak sunflower conjecture.

Theorem: The weak sunflower conjecture implies that the CW90 conjecture is false. 

It follows that CW90 conjecture is in conflict both with the Erdos Rado sunflower conjecture and with the strong cup set conjecture.

Theorem: The strong cup set conjecture implies that the strong UPS conjecture is false.

While two family theorems are quite popular in extremal combinatorics (see this post and this one), CKSU’s two family conjecture is still rather isolated from other combinatorics.

What to believe?
This is a nice topic for discussion.

In today’s post, I will discuss a little-known combinatorics paper by E.N. Gilbert from 1965, in which he independently discovered the “logarithmic Welch” construction of Costas arrays.  Costas arrays are named after the late IEEE fellow John Costas, whose seminal paper on what are now called Costas arrays appeared, coincidentially, in 1965, the same year as Gilbert’s paper.  I had never heard of Costas arrays until just a few weeks ago, when I needed a combinatorial object with their properties for a problem I am trying to solve about error-prevention in molecular self-assembly.  So I approached the literature in a nonstandard way, found Gilbert’s paper, and eventually wrote experts on Costas arrays to confirm that Theorem 6 of Gilbert’s Latin Squares Which Contain No Repeated Digrams did indeed produce a construction that independently appeared in the literature “for the first time” in 1982.  Therefore, my objective with this blog post is twofold: (1) to make better known an area of combinatorics that may be familiar to information theorists but not to computer scientists; and (2) to change in a small way the intellectual history of this area, so Gilbert is recognized as a co-inventor of an important class of combinatorial designs.  (ADDED LATER: It appears I may have accomplished (2).  The Wikipedia page on Gilbert now states that he was a co-inventor of Costas arrays, and cites this blog entry as justification.  This is my first Wikipedia citation, to my knowledge.  Somewhere along the way, I seem to have morphed from off-the-wall commentator to reliable source.)

First, though, a quick pointer for anyone interested in DNA computation: Dave Doty just contributed an entry to the CSTheory Community Blog on the DNA Computing conference that took place last month at CalTech.  Dave was on the local arrangements committee, and, in his post, he talks about both technical results presented at the conference, and suggestions for organization of future CS conferences.  Good stuff.

Latin squares and the design of experiments

Consider the following Latin square, Square 1:

A Latin square, of course, is an square with entries from an alphabet , such that each letter of appears exactly once in each row, exactly once in each column, and there are only letters, i.e., .  Latin squares find applications in group theory, error-correcting codes, and the design of experiments.  However, as Gilbert points out in his paper, Square 1 is not a good Latin square on which to base experiments, because pairs of letters (i.e., digrams) repeat in multiple rows and columns of the square (examples: AB, BC).  Quoting from the paper:

The [elements of the Latin square] represent stimuli to be presented once each to a subject in a time sequence…. Each row or column of a Latin square can supply a suitable order of presentation.  However, if the experiment is to be repeated several times using different rows of a Latin square, the square should have rows which resemble each other as little as possible…. If a stimulus can influence a subject’s response to the next stimulus then no two orders of presentation should repeat the same pair of stimuli consecutively.

Therefore, we would like to be able to construct a Latin square such that any adjacent pair of letters appears at most once horizontally, and at most once vertically.  Gilbert solves this problem by constructing an addition square from two permutations with distinct differences.

Permutations with distinct differences

Consider the two permutations and .  Permutation has the property that .  Permutation has the property that .  In other words, all the differences between elements that are distance-1 from each other are distinct.  A permutation with this property is called a permutation with distinct differences, or a PDD.  In this example, is a PDD, while is not.

With two PDD’s and on elements, it is possible to construct an  Latin square by placing the element at location .  A Latin square produced in this way is called an addition square. Suppose a digram appears twice in an addition square, at locations , and .  Then the following two congruences must hold.

Taken together, those congruences imply

,

which is impossible if is a permutation with distinct differences.  By a similar argument, if is a permutation with distinct differences, a vertical digram cannot repeat in the addition square either.

It is not hard to produce a PDD on an even number of elements.  Suppose .  Then the following permutation is a PDD:

Gilbert uses two PDD’s on 8 elements to produce Square 2:

Square 2 contains no repeated digrams, either horizontally or vertically.  However, it contains horizontal and vertical repeats of a different form: , where is a “don’t-care” symbol that repeats times.  For example, repeats in the rows of Square 2.  In order to eliminate this type of repetition, Gilbert constructs addition squares using a new tool: Costas arrays.

Costas arrays

A Costas array is a special kind of PDD, one in which every difference between every pair of elements apart is distinct, for each .  (A PDD only requires this of elements that are spaced 1 apart.)  Scott Rickard maintains the website costasarrays.org, to centralize information on research into Costas arrays.  I will quote from the historical overview on that site.

In the 1960’s, Dr. John P. Costas, motivated by a novel SONAR application, began searching for permutation matrices with ideal auto-ambiguity properties. By hand, he found examples of such matrices of size up to N = 12. Unable to find one of size 13, he contacted Professor Solomon Golomb who then provided generation techniques based on the theory of finite fields for creating these matrices, dubbed Costas arrays. The generation methods produce Costas arrays for infinitely many N, but not all N. For example, the techniques can be used to generate arrays for all N ≤ 31, but no Costas array of size N = 32 or N = 33 has been found. Computer search has enumerated all Costas arrays of size N ≤ 29, but the exponential growth of the search space prohibits extending these results much further with current computational capabilities. After nearly 40 years of research, the first question concerning Costas arrays remains open: Do Costas arrays exist for all N?

A discussion starting from that quote could proceed in many different directions, but I want to bring this blog entry to a close, so I will limit myself to a sketch of Gilbert’s Theorem 6, in which he independently discovers a method of generating Costas arrays, and then he applies them to the creation of addition squares.

Theorem: Suppose is a prime.  Let be a primitive root of the prime and define a permutation by the congruence .  Then is a Costas array.

Of course, Gilbert did not call a Costas array.  He called it a permutation with distinct differences apart for every .  This theorem turns out to be essentially identical to a theorem proved in 1982 by Welch and Golomb that describes the “logarithmic Welch” construction of Costas arrays.  (Welch came up with the method as a heuristic to produce Costas arrays, and Golomb proved rigorously that it worked.)

Taking , and using the primitive roots 3 and 5 of GF(7), Gilbert produces Square 3, an addition square from those two Costas arrays:

Square 3 has the property that no digrams repeat in any row or column, where a digram is now defined as the same two letters separated by the same number of spaces.

Acknowledgements

Scott Rickard and Konstantinos Drakakis, both experts on Costas arrays, verified for me that I wasn’t just seeing things, and in fact, Gilbert’s construction was an overlooked independent discovery.  Before I knew the name “Costas array,” several people on CSTheory and MathOverflow put up with confused questions I asked (CST question, another CST question, MO question).  I also had a helpful email correspondence with Sergey Kitaev.  When all was said and done, though, I thought one day to type “no repeating digrams” into Google, instead of “no repeating pairs.”  That brought me to Gilbert’s paper, and searching on the phrase “permutations with distinct differences” brought me to the magic term “Costas arrays.”  Hopefully some applications of this proof technology to self-assembly will be appearing soon at a conference near you.

Gilbert, E. (1965). Latin Squares which Contain No Repeated Digrams SIAM Review, 7 (2) DOI: 10.1137/1007035

Tagged: combinatorics, Costas arrays, history of mathematics, information theory, Latin squares

Alantha Newman and Alexandar Nikolov disproved a few months ago one of the most famous and frustrating open problem in discrepancy theory: Beck’s 3-permutations conjecture. Their paper  A counterexample to Beck’s conjecture on the discrepancy of three permutations is already on the arxive since April. (I was slow to get the news. Yuval Peres who heard it from Prasad Tetali told me about it today. You can read about it already on Joel Spencer’s homepage. Joel had offered 100$ prize for solving the conjecture that Alantha and Alexandar collected.)

The paper’s abstract tells the story.

Our previos post gives the basic definition of discrepancy of a hypergraph (=set-system), and describes a theorem by Beck and Fiala.

Abstract: Given three permutations on the integers 1 through n, consider the set system consisting of each interval in each of the three permutations. Jozsef Beck conjectured (c. 1987) that the discrepancy of this set system is O(1). We give a counterexample to this conjecture: for any positive integer , we exhibit three permutations whose corresponding set system has discrepancy . Our counterexample is based on a simple recursive construction, and our proof of the discrepancy lower bound is by induction. This example also disproves a generalization of Beck’s conjecture due to Spencer, Srinivasan and Tetali, who conjectured that a set system corresponding to l permutations has discrepancy .

The Question
Suppose that you want to send a message so that it will reach all vertices of the discrete -dimensional cube. At each time unit (or round) you can send the message to one vertex. When a vertex gets the message at round all its neighbors will receive it at round .

We will denote the vertices of the discrete -cube by vectors of length . The Hamming distance between two such vertices is the number of coordinates they differ and two vertices are neighbors if their Hamming distance equals 1. 

The question is

how many rounds it will take to transmit the message to all vertices?

Here is a very simple way to go about it: At round 1 you send the message to vertex (-1,-1,-1,…,-1). At round 2 you send the message to vertex (1,1,…,1). Then you sit and wait. With this strategy it will take rounds.

Test your intuition: Is there a better strategy?

The Answer: NO
The answer to the question posed in test you intuition (14) is no. There is no better strategy. The question was originated in Intel. It was posed by Joe Brandenburg and David Scott, and popularized by Vance Faber. The answer was proved by Noga Alon in the paper Transmitting in the n-dimensional cube, Discrete Applied Math. 37/38 (1992), 9-11. The result is closely related to combinatorial discrepancy theory and the proof is related to the argument in the Beck-Fiala theorem and a related lemma by Beck and Spencer. This is a good opportunity to present the Beck-Fiala Theorem.

The general form of a discrepancy problem
Let be a hypergraph, i.e., a collection of subsets of a ground set . is also called the set of vertices of the hypergraphs and the subsets in are also called edges.

The discrepancy of , denoted by  is the minimum over all functions of the maximum over all  of

.  

The Erdős Discrepancy Problem (EDP) asks about the following particular hypergraph: The vertices are {1,2,…,n} and the edges are sets of vertices which form arithmetic progressions of the form (r,2r,3r,…kr}. EDP was extensively discussed and studied in polymath5. Here is the link of the first post. Here are links to all polymath5 posts.  Here is the link to polymath5 wiki.

The Beck-Fiala theorem
Theorem (Beck-Fiala): If every element in is included in at most  edges  of   then .

Before proving this theorem we mention that it is a famous open conjecture to show that actually

Proof: Consider the following process such that in every step every element  of is assigned a real value in the interval [0,1]. At each step of the process some elements in are assigned -1 or +1 and such assignements will not change at later steps. We call such assinements determined values. A set is relevant at step if it contains more than  undetermined values. The crucial property (P) we want to mentain along the process is that at every step the sum of values for every relevant set in is precisely 0.

At the first step we give all elements the value 0.

When we reach a step where all sets S in A become irrelevant we stop. Now if we will define by replacing every undetermined value by either +1 or -1 the  sum for every set will be smaller than .

Lemma: At each step the number of undetermined values is larger than the number of relevant sets.

Proof of the lemma: This follows immediately from the fact that every relevant set contains at least undetermined values while every element in is included in at most edges of . 

We return to the proof of the theorem. Suppose that at some step there are relevant sets .  We already have a vector of weights  such that all weights are in the interval [-1,1] and the sum of weights over every relevant set is 0.  

Now, ignore the determined values, assign a variables to every undetermined value and consider the system of equations in which for every relevant set the sum of variables in the set is 0. By the lemma we have more equations than variables. Since the all 0 vector solves our system of equations there is also another nontrivial solution . Consider where is a small positive value.  When we gradually increase  we reach a new solution with one additional determined value.

An even more general form of the discrepancy problem
Question: Let be subsets of a ground set A={1,2,,,n} and let be integers. Is there a function such that for every

?

In the ordinary combinatorial discrepancy problem we assume all these s are the same.

The following result of Beck and Spencer which addresses a special case of the more general discrepancy problem admits a simple linear algebra proof similar to the proof of the Beck Fiala theorem described above: 

Lemma (Beck-Spencer):  Let $A=(a_{i,j})$ be an by matrix where each entry is either a 1 or a -1. Then there is a vector of length n with latex \pm 1$ entries, such that for each the scalar product od with the th row of is, in absolute value strictly less than .

Let me simply bring the argument for this lemma and the derivation of the negative answer to the cube transmission problem from Alon’s paper.

Proof of Beck-Spencer’s lemma

The negative answer to the cube transmission problem follows from Beck-Spencer lemma as follows: