# 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.

- Every term in the array, not on the first line, is the product of the two terms above it.
- The numbers of 1's and of -1's in the array should be equal.

**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**

- 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.
- The case m = 3^k: description of the solution of Molluzzo's problem by Chappelon.
- The case m odd: description of the solution of the weak Molluzzo's problem by Chappelon.
- The case m = 4: description of the solution of Molluzzo's problem by Chappelon and Eliahou.
- A parenthesis on the polynomial method, which has many combinatorial applications and might be useful for making further progress on Molluzzo's problem.