MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Construct a family of sets $A_n$ such that $$|A_n|=\Theta\left((\log n)^2\right)$$ and the elements of $A_n$ are chosen uniformly at random mod $n$.

Say that a set $S$ represents $m\mod{n}$ if there are some $s,t\in S$ such that $$\frac{s}{t}\equiv m\mod{n}$$

Conjecture: For any $m$, there is an $A_n$ that represents $m\mod{n}$ almost surely

I formulated this conjecture while working on a somewhat tangentially related problem. My primary interest is to gain a heuristic understanding of whether or not such a result is possible. In addition, I would like to learn more about the kinds of techniques employed to solve problems of this nature.

share|cite|improve this question
I think this works even if $|A_n|=2$ for each $n$ (or even if you just work with prime $n$). This would follow from the 2nd Borel-Cantelli lemma (the probability that $m$ is represented is at least $1/n$ and the representability by $A_n$ is independent of representability by other sets). – Anthony Quas May 29 '13 at 0:39
Thanks for the response. I am realizing that what I formulated here was weaker than what I intended. Do you mind if I tweak my original question a bit? – pre-kidney May 29 '13 at 2:35
Updated version: Consider a specific family $$\{A_n\}\qquad A_n\in\mathbb{Z}/n\mathbb{Z}$$with the same growth condition as before. Conjecture: For any $m$, there is an $A_n$ that represents $m\mod{n}$. – pre-kidney May 29 '13 at 2:43
If I understand your modified question correctly, you can construct $A_n$ that don't represent $m$ by a greedy algorithm: given $s_1,\dots,s_k$ already in $A_n$, there are $\phi(n)-k$ other possible choices for $s_{k+1}$ among invertible elements $\mod n$, and at most $2k$ of them result in the extended set representing $m$. So you can find an $A_n$ of size about $\phi(n)/3$ that doesn't represent $m$. (And $\phi(n)$ is always larger than a constant times $n/\log\log n$, so much bigger than $\log^2n$.) – Greg Martin May 29 '13 at 6:00

Your Answer


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

Browse other questions tagged or ask your own question.