Large subsets of Z m n without arithmetic progressions.

For integers m and n, we study the problem of finding good lower bounds for the size of progression-free sets in ( Z m n , + ) . Let r k ( Z m n ) denote the maximal size of a subset of Z m n without arithmetic progressions of length k and let P - ( m ) denote the least prime factor of m. We construct explicit progression-free sets and obtain the following improved lower bounds for r k ( Z m n ) :If k ≥ 5 is odd and P - ( m ) ≥ ( k + 2 ) / 2 , then r k ( Z m n ) ≫ m , k ⌊ k - 1 k + 1 m + 1 ⌋ n n ⌊ k - 1 k + 1 m ⌋ / 2 . If k ≥ 4 is even, P - ( m ) ≥ k and m ≡ - 1 mod k , then r k ( Z m n ) ≫ m , k ⌊ k - 2 k m + 2 ⌋ n n ⌊ k - 2 k m + 1 ⌋ / 2 . Moreover, we give some further improved lower bounds on r k ( Z p n ) for primes p ≤ 31 and progression lengths 4 ≤ k ≤ 8 .

Exponentially larger affine and projective caps.

In spite of a recent breakthrough on upper bounds of the size of cap sets (by Croot, Lev and Pach and by Ellenberg and Gijswijt), the classical cap set constructions had not been affected. In this work, we introduce a very different method of construction for caps in all affine spaces with odd prime modulus p. Moreover, we show that for all primes p ≡ 5 mod 6 with p ⩽ 41 , the new construction leads to an exponentially larger growth of the affine and projective caps in AG ( n , p ) and PG ( n , p ) . For example, when p = 23 , the existence of caps with growth ( 8.0875 … ) n follows from a three-dimensional example of Bose, and the only improvement had been to ( 8.0901 … ) n by Edel, based on a six-dimensional example. We improve this lower bound to ( 9 - o ( 1 ) ) n .

Sums of four and more unit fractions and approximate parametrizations.

We prove new upper bounds on the number of representations of rational numbers m n as a sum of four unit fractions, giving five different regions, depending on the size of m in terms of n . In particular, we improve the most relevant cases, when m is small, and when m is close to n . The improvements stem from not only studying complete parametrizations of the set of solutions, but simplifying this set appropriately. Certain subsets of all parameters define the set of all solutions, up to applications of divisor functions, which has little impact on the upper bound of the number of solutions. These 'approximate parametrizations' were the key point to enable computer programmes to filter through a large number of equations and inequalities. Furthermore, this result leads to new upper bounds for the number of representations of rational numbers as sums of more than four unit fractions.

Caps and progression-free sets in Z m n.

We study progression-free sets in the abelian groups G = ( Z m n , + ) . Let r k ( Z m n ) denote the maximal size of a set S ⊂ Z m n that does not contain a proper arithmetic progression of length k. We give lower bound constructions, which e.g. include that r 3 ( Z m n ) ≥ C m ( ( m + 2 ) / 2 ) n n , when m is even. When m = 4 this is of order at least 3 n / n ≫ | G | 0.7924 . Moreover, if the progression-free set S ⊂ Z 4 n satisfies a technical condition, which dominates the problem at least in low dimension, then | S | ≤ 3 n holds. We present a number of new methods which cover lower bounds for several infinite families of parameters m, k, n, which includes for example: r 6 ( Z 125 n ) ≥ ( 85 - o ( 1 ) ) n . For r 3 ( Z 4 n ) we determine the exact values, when n ≤ 5 , e.g.  r 3 ( Z 4 5 ) = 124 , and for r 4 ( Z 4 n ) we determine the exact values, when n ≤ 4 , e.g.  r 4 ( Z 4 4 ) = 128 . With regard to affine caps, i.e. sets without 3 points on a line, the new methods asymptotically improve the known lower bounds, when m = 4 and m = 5 : in Z 4 n from 2 . 519 n to ( 3 - o ( 1 ) ) n , and when m = 5 from 2 . 942 n to ( 3 - o ( 1 ) ) n . This last improvement modulo 5 appears to be the first asymptotic improvement of any cap in AG(n, m), when m ≥ 5 over a tensor lifting from dimension 6 (see Edel, in Des Codes Crytogr 31:5-14, 2004).

Romanov type problems.

Romanov proved that the proportion of positive integers which can be represented as a sum of a prime and a power of 2 is positive. We establish similar results for integers of the form n = p + 2 2 k + m ! and n = p + 2 2 k + 2 q where m , k ∈ N and p, q are primes. In the opposite direction, Erdos constructed a full arithmetic progression of odd integers none of which is the sum of a prime and a power of two. While we also exhibit in both cases full arithmetic progressions which do not contain any integers of the two forms, respectively, we prove a much better result for the proportion of integers not of these forms: (1) The proportion of positive integers not of the form p + 2 2 k + m ! is larger than 3 4 . (2) The proportion of positive integers not of the form p + 2 2 k + 2 q is at least 2 3 .

Independence and interdependence in collective decision making: an agent-based model of nest-site choice by honeybee swarms.

Condorcet's jury theorem shows that when the members of a group have noisy but independent information about what is best for the group as a whole, majority decisions tend to outperform dictatorial ones. When voting is supplemented by communication, however, the resulting interdependencies between decision makers can strengthen or undermine this effect: they can facilitate information pooling, but also amplify errors. We consider an intriguing non-human case of independent information pooling combined with communication: the case of nest-site choice by honeybee (Apis mellifera) swarms. It is empirically well documented that when there are different nest sites that vary in quality, the bees usually choose the best one. We develop a new agent-based model of the bees' decision process and show that its remarkable reliability stems from a particular interplay of independence and interdependence between the bees.