Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
3  
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 at 16:51
3  
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 at 18:04
    
@guest That is true... Thank you for pointing out! –  SJY May 12 at 18:30
    
Thank you very much for all the comments and answers! –  SJY May 12 at 18:35

5 Answers 5

up vote 7 down vote accepted

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

share|improve this answer

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.

share|improve this answer
    
In some contexts, it may also be natural to require that Gower's uniformity norms of the indicator function should be small. –  Feanor Jun 24 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).

share|improve this answer
    
Thank you! I will look into TAo &Vu also. –  SJY May 12 at 18:33

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.