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

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|improve this question
2  
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? –  vlv 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}$. –  vlv 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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.