3
$\begingroup$

I've been reading about cap sets in $\mathbb{F}_3^d $ over the past couple of days and wondered why we can only find bounds, as opposed to exact values, for (maximum) sizes of cap sets for $d>6$. The proofs are somewhat unclear to me (as a physics student) so I couldn't extrapolate from there.

The largest sizes of cap sets in $\mathbb{F}_3^d$ for $d \leq 6$ are listed at https://oeis.org/A090245.

Improve this question
$\endgroup$
5
  • $\begingroup$ Capsets... where? In $\mathbb F_p^d$? Is $d$ the dimension? Maybe, just because for $d\le 5$ the exact values are known? $\endgroup$
    – Seva
    Commented Dec 10, 2023 at 19:11
  • $\begingroup$ Yes, sorry about that. Just edited for clarification. $\endgroup$
    – 15948238
    Commented Dec 10, 2023 at 19:48
  • $\begingroup$ I am still puzzled. Why do you believe that "we can only find bounds for sizes of cap sets for $d>6$"? $\endgroup$
    – Seva
    Commented Dec 10, 2023 at 19:58
  • $\begingroup$ Bounds as opposed to exact values is what I meant. $\endgroup$
    – 15948238
    Commented Dec 10, 2023 at 20:56
  • 6
    $\begingroup$ It is not uncommon for exact values of these kind of problems of counting combinatorial objects satisfying certain constraints to be known only for small parameter values. The issue is just that brute force searching becomes computationally infeasible beyond a certain level, and there are not techniques much better than brute force. This is related to the whole idea of polynomial time vs. NP computational problems, and also "combinatorial explosion." Maybe more can be said for this particular problem of cap sets, but I doubt there is anything to unique to it. $\endgroup$
    – Sam Hopkins
    Commented Dec 11, 2023 at 1:05

2 Answers 2

Reset to default
3
$\begingroup$

Paul Erdős explained this very well here. The link leads to an excerpt from the 1993 movie N is a number: a portrait of Paul Erdős by George Paul Csicsery. The quote appeared earlier in a 1990 Scientific American article by Ronald Graham and Joel Spencer in the following form: "Suppose aliens invade the earth and threaten to obliterate it in a year's time unless human beings can find the Ramsey number for red five and blue five. We could marshal the world's best minds and fastest computers, and within a year we could probably calculate the value. If the aliens demanded the Ramsey number for red six and blue six, however, we would have no choice but to launch a preemptive attack."

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ @OscarLanzi "should do" is a strong expression. This is a question-and-answer site, and I know my way around. For what it is worth, I extended my answer, check it out. Feel free to add a better answer. $\endgroup$
    – GH from MO
    Commented Dec 11, 2023 at 17:00
  • $\begingroup$ I have tried adding my own summary based on what I saw, but I have to wait for the edit to be accepted. If so then I can upvote. $\endgroup$
    – Oscar Lanzi
    Commented Dec 11, 2023 at 17:24
  • 1
    $\begingroup$ @OscarLanzi I rejected your edit, because I wanted to keep Erdős's words intact (there is no need to paraphrase or summarize). Please add your comments/thoughts as a separate answer (I will upvote it within 24 hours). Thanks! $\endgroup$
    – GH from MO
    Commented Dec 11, 2023 at 17:28
  • 1
    $\begingroup$ I was able to see the video. Both that and Oscar's comments were very helpful, thank you! $\endgroup$
    – 15948238
    Commented Dec 11, 2023 at 18:17
5
$\begingroup$

To explain the link given by GH from MO (simply because it may die): Essentially, the computations required to make the proof are known, but their complexity grows exponentially* with increasing $d$. The complexity thereby outruns the capacity of our computers to date at a relatively small value of $d$.

*According to comments (Terry Tao), known algorithms have doubly exponential runtimes, that is $a^{b^d}$ where both $a,b>1$ and the red/blue number is $d$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I understand now, thank you for the help! $\endgroup$
    – 15948238
    Commented Dec 11, 2023 at 18:17
  • 2
    $\begingroup$ It should be pointed out that the situation is even worse: all known algorithms to compute the size of the maximal cap set are doubly exponential in $d$, rather than singly exponential. For instance, naive brute force search has the runtime of $2^{3^d}$. Even the $P=NP$ conjecture would "merely" cut this runtime down to singly exponential. $\endgroup$
    – Terry Tao
    Commented Aug 7 at 15:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .