Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The card game Set lead to the following question. Lets call a subset $A$ of $(\mathbb{Z}/3)^n$ dependent, if there is $\{x,y,z\}\subset A$ with $x+y+z=0$. (So unlike the case of linear dependence we are not allowing any coefficients here).

Let $f(n)$ denote the maximal size of a independent subset of $(\mathbb{Z}/3)^n$. Is there an explicit expression / a recursion for $f(n)$? Can anything be said about its asymptotic behaviour (like $f\in O(c^n)$ for some minimal $c$)?

As $\{0;1\}^n$ is independent, we know that $f(n)\ge 2^n$. And so $c\ge 2$. The card game set deals with the case $n=4$ and $f(4)=20$ if i remember correctly.

share|improve this question
    
You may be interested in some of the discussion around Polymath1, which I believe tackles similar questions. –  Qiaochu Yuan Oct 6 '10 at 12:01
    
$f(4)=20$ is correct--that is, 20 is the minimum number of SET cards needed to guarantee a "set" in the context of the game. –  Isaac Oct 6 '10 at 16:23
    
I am a bit confused. Both answers I got are contradicting each other, as the given recursion does not satisfy the claimed lower bound c>2. Furthermore In this presentation is sounded like its unknown,whether this recursion holds (it is in the chapter further work and it is followed by a ?-sign). Anyhow I am a bit confused right now. –  HenrikRueping Oct 7 '10 at 0:16
    
You claimed c≥2, which the formulas I gave do satisfy (as it is O(2^n), so c=2). On a second look, you're right that the presentation to which I linked does not quite make it clear whether or not these formulas (which are not recursive) are correct, but that was how I read it and the formulas do seem to work for n=2, 3, 4, 5, and 6. –  Isaac Oct 7 '10 at 0:40
    
"We have a lower bound of order c^n for some c > 2" I think this statement in harrisons answer contradicts the suggested formula. –  HenrikRueping Oct 7 '10 at 9:37
add comment

2 Answers

up vote 2 down vote accepted

Mathematicians call these "independent sets" capsets, and they're fairly widely studied. But surprisingly, we don't know much about their asymptotic behavior! We have a lower bound of order c^n for some c > 2; and we have an upper bound of order about 3^n/n (although this is not in the least trivial to prove!) Most mathematicians seem to suspect that the upper bound can't be improved to c^n for c strictly less than 3, but no one's sure how to prove this.

For more information (perhaps a little out-of-date, but I don't think much has changed) see Terry Tao's discussion.

share|improve this answer
add comment

Based on this presentation (PPT; Google-based HTML conversion), I think a formula for your $f(n)$ is: $$f(n)=\begin{cases} \frac{2^{n+2}-4}{3} & \text{ if }n\text{ is even} \\ \frac{2^{n+2}-5}{3} & \text{ if }n>1\text{ is odd} \end{cases}$$

share|improve this answer
add comment

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.