Fundamentals of Computing and Discrete Mathematics

Shalom Eliahou

Université du Littoratl - France

December 2011

Distinguished Lecture Colloquium

Schur numbers and Boolean satisfiability

A set of natural numbers is said to be sum-free if it contains no elements a, b, c satisfying a+b = c. It is said to be weakly sum-free if it contains no three distinct elements a, b, c satisfying a + b = c. Given integers k, n 1, can one partition the set {1, 2, ... , n} into k sum-free parts? A theorem of Schur in 1916, linked to Fermat’s Last Theorem, states that the answer is positive only if n does not exceed a certain maximal threshold S(k). Similarly, there exists a maximal threshold n WS(k) above which it is impossible to partition the set {1, 2, . . . , n} into k weakly sum-free parts. These are typical Ramsey-type results. The exact values for S(k) and WS(k) are known only for k 4. In this talk, we shall explain the mysteries surrounding the cases k = 5 and 6, and the recent progress obtained by translating the problem into a Boolean satisfiability one and using computer SAT solvers.

TUCS Short Course

Recent results on a problem of Molluzzo in combinatorial number theory

In the mid 50's, Hugo Steinhaus asked a question about the existence of triangular arrays of length n, with coefficients 1 and -1, satisfying the following two conditions.

  1. Every term in the array, not on the first line, is the product of the two terms above it.
  2. The numbers of 1's and of -1's in the array should be equal.
An obvious necessary condition for (2) to hold is that the number of entries in the array should be even. The question of Steinhaus was: is this necessary condition also sufficient to ensure the existence of a triangle of side length n satisfying these two properties? The problem was first solved positively by Heiko Harborth in 1972. Nowadays, three more solutions are known, each with its own method of construction and with some special additional properties. The original problem of Steinhaus may be restated in terms of triangular arrays with coefficients in {0,1}, viewed as the set of integers mod 2. It has been later generalized by John Molluzzo in the late 70's, as follows. In the group Z/mZ of integers modulo m, where m is a fixed positive integer, consider a finite sequence s of length n. This sequence gives rise to a triangular array by Pascal's rule, namely: its first row is s, and the coefficient in each subsequent row is the sum of the two coefficients above it. The triangle thus obtained is called the Steinhaus triangle of s. The problem of Molluzzo, generalizing that of Steinhaus, is the following

Problem. Let m be a positive modulus. For which n does there exist a sequence of length n in Z/mZ whose associated Steinhaus triangle is balanced, i.e. contains each element of Z/mZ with the same multiplicity?

Again, an obvious necessary existence condition is that the binomial coefficient (n+1 choose 2) should be divisible by m. Is this necessary existence condition also sufficient? As it is, the problem seems to be very difficult. Currently, it is fully solved only for m = 2, 3^k, 4, 5 and 7. A weaker version of Molluzzo's problem asks whether, for each modulus m, there are infinitely many sequences in Z/mZ whose Steinhaus triangle is balanced. The currently smallest open case is m = 6. The purpose of this course is to explain what is known concerning these problems, including many recent results due to Jonathan Chappelon.

Contents
  1. The case m = 2: description of the four known solutions of the original problem of Steinhaus, and of their method of construction. This part will include a few related experiments in Mathematica.
  2. The case m = 3^k: description of the solution of Molluzzo's problem by Chappelon.
  3. The case m odd: description of the solution of the weak Molluzzo's problem by Chappelon.
  4. The case m = 4: description of the solution of Molluzzo's problem by Chappelon and Eliahou.
  5. A parenthesis on the polynomial method, which has many combinatorial applications and might be useful for making further progress on Molluzzo's problem.
Last modified: