What makes a set random?

Question

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 Erdős and Rényi, where they proved the existence of a "thin" $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!

Answer 1

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

Answer 2

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.

Answer 3

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

Answer 4

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.

Answer 5

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.