# What makes a set random?

There are many results in number theory, where the existence of some $B \subseteq \mathbb{N}$ with certain properties is proved by a probabilistic argument employing "random sets". One such example would be the result of Erdos and Renyi, where they proved the existence of a "think" $B_2[g]$ sequence.

My question is are there certain known properties, so that if $A \subseteq \mathbb{N}$ satisfies them, then $A$ is considered to behave like a random set? or what properties would make $A$ considered to be close to being random? Thank you!

• Not an expert, but as I imagine this question can be answered from the point of view of computability. The rough idea being that a set is random if the "size" of any algorithm describing it is not smaller than its own "size". – Dimitri Chikhladze May 10 '14 at 16:51
• Just a caution - the word random has had a major redefinition between your first and second paragraphs. In the first it is chosen from some probability distributions, while is more a question of complexity. – guest May 10 '14 at 18:04
• @guest That is true... Thank you for pointing out! – SJY May 12 '14 at 18:30

One set of answers to these questions is given by the theory of algorithmic randomness.

Additive number theory (or additive combinatorics) makes a lot of use of quasirandom sets.

Suppose that we are looking for an arithmetic progression in some dense subset $A$ of $[n] = \{1, \ldots, n\}$. If $A$ resembles a random set, then finding an AP is easy, so $A$ must have some structure. That structure turns out to be that $A$ is slightly denser on some subprogression of $A$ (e.g. $\{2, 4, 6, \ldots, n\}$, so we can repeat the argument on this subset with a stronger assumption. At a very high level, this is one way that Szemerédi's theorem can be proved.

So one way of characterising quasirandom sets would be to say that they have about the density you would expect on all subprogressions. This property can be quantified using various analytic tools: for example, we might say that a set is quasirandom if (most of) the fourier coefficients of its indicator function are small.

Tao and Vu's book has already been recommended to you, and would have a lot more detail on this sort of thing.

• In some contexts, it may also be natural to require that Gower's uniformity norms of the indicator function should be small. – Jakub Konieczny Jun 24 '14 at 15:19

Most of the stuff I've seen involves every element in $\mathbb{N}$ having a probability of being in the set $B$.

Another way I've seen (in Tao & Vu) is that we deterministically generate a set, randomly select some element and then transform this deterministic set by this random element (by addition or multiplication or something similar).

Armchair definition:

If there exists no known compression algorithm, written for a general case, that can convert a binary encoding of the set members in exact order to a one-to-one transformed set of smaller size of members, of identical type, as the origin.

A random set should be a sort of generic set, in a similar sense as I outlined in my attempt to characterize a generic element quantifier: "A generic element $\xi$ would basically satisfy $(\exists xf(x)\neq g(x))\to f(\xi)\neq g(\xi)$ for all functions $f$, $g$ relevant to the current context." In a comment, this hand-wavy characterization is replaced by more mathematical meaningful statement: "The interior of the set of all $\xi$ for which the proposition is true should be dense in $\mathbb R^n$." Subsets of $\mathbb N$ are closely related to elements of the interval $[0,1)$, hence these thoughts are related to this question. But note that $f$ and $g$ are now functions mapping subsets of $\mathbb N$ to subsets of $\mathbb N$. Every function mapping natural numbers to natural numbers also induces such a function, but there are many more such functions not induced in this way.

I like to think of the set $P$ of prime numbers as a quasi-random set. The reason is that all elements satisfying certain multiplicative equations have been removed from $P$. This make it quite likely that $P$ will satisfy $f(P)\neq g(P)$ for all functions $f$, $g$ relevant to "certain" contexts. It's only quasi-random, because there might be (some rare) contexts where $P$ fails to be a generic element.