Let $S_1,S_2,\ldots S_k$ be a sequence of sets. We will call this sequence expanding if $S_i$ is not covered by $S_1,\ldots S_{i-1}$ i.e. $S_i$ contains at least one new element. Let $C_p$ be a cyclic group of size prime order $p$.

It is easy to show that for every $A\subset C_p$ there exists at least $k=\frac{p}{|A|}$ elements $a_1,\ldots a_k$, such that the sets $A+a_i$ are expanding.(Since each time we cover at most |A| new elements and we can cover all elements)

My question is if it is possible to improve this bound for $A$ of size at most $p/2$ to $k=\frac{p\log|A|}{|A|}$?

  • $\begingroup$ Here is important that group is of prime order. Else if A is $pC_m$, where p divisor of $m$ than $k=\frac{m}{|A|}$ $\endgroup$ – Klim Efremenko Jan 30 '12 at 16:13
  • $\begingroup$ Let $a_0,a_1,a_2,\dots,a_k$ be a list of elements from $C_p$, $A \subset C_p$ and $A_i=A+a_i.$ Are you looking to have $A_0,A_0\cup A_1 ,A_0\cup A_1 \cup A_2 \dots?$ an expanding sequence? $\endgroup$ – Aaron Meyerowitz Jan 30 '12 at 18:25
  • $\begingroup$ By the definition $A_0,A_1,\ldots $ expanding if and only iff $A_0,A_0\cup A_1,A_0\cup A_1\cup A_2,…$ is expanding. I am looking that $A_1,A_2,\ldots$ is expanding. Where $A_i=A+a_i$ $\endgroup$ – Klim Efremenko Jan 30 '12 at 19:03

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.