Abstract:
|
We study threshold functions for the existence of solutions to linear systems of equations in random sets and present a unified framework which includes arithmetic progressions, sum-free sets, Bh[g]Bh[g]-sets and Hilbert cubes. In particular, we show that there exists a threshold function for the property “AAcontains a non-trivial solution of M·x=0M·x=0” where AA is a random set and each of its elements is chosen independently with the same probability from the interval of integers {1,…,n}{1,…,n}. Our study contains a formal definition of trivial solutions for any linear system, extending a previous definition by Ruzsa when dealing with a single equation. Furthermore, we study the distribution of the number of non-trivial solutions at the threshold scale. We show that it converges to a Poisson distribution whose parameter depends on the volumes of certain convex polytopes arising from the linear system under study as well as the symmetry inherent in the structures, which we formally define and characterize.
Juanjo Rué was partially supported by the FP7-PEOPLE-2013-CIG Project CountGraph (ref. 630749), the Spanish MICINN Projects MTM2014-54745-P and MTM2014-56350-P, the DFG within the Research Training Group Methods for Discrete Structures (ref. GRK1408), and the Berlin Mathematical School. Christoph Spiegel was supported by a Berlin Mathematical School Scholarship. Ana Zumalacárregui is supported by the Australian Research Council Grant DP140100118. The first and third authors started this project while financed by the MTM2011-22851 Grant (Spain) and the ICMAT Severo Ochoa Project SEV-2011-0087 (Spain). |