We give tight lower bounds for the size of depth-3 circuits with limited bottom fanin computing symmetric Boolean functions. We show that any depth-3 circuit with bottom fanin $k$ which computes the Boolean function $EXACT_{n/(k+1)}^{n}$, has at least $(1+1/k)^{n+\O(\log n)}$ gates. We show that this lower bound is tight, by generalizing a known upper bound on the size of depth-3 circuits with bottom fanin 2, computing symmetric Boolean functions.
The upper bounds claimed for general symmetric functions (Lemma 3, Theorem 2, Corollary 1) are unfortunately incorrect. As of June 2023, it appears to still be open (for example) whether MAJORITY has depth-3 circuits of size $2^{O(sqrt{n})}$ or not, and whether MAJORITY requires depth-3 bottom fan-in k circuits of size $2^{\Omega(n \log k)/k}$. (However, it does appear to be true that $EXACT_{n/k}$ has a depth-3 bottom fan-in $k$ circuit of size $2^{O(n/k)}$, as claimed in the abstract.)
I am leaving a comment because this preprint often appears in web searches for circuit upper bounds on symmetric functions, and it does not seem well-known that these problems are still open.
The source of the problem was highlighted in footnote 2 of "The Composition Complexity of Majority" (CCC 2022, https://drops.dagstuhl.de/opus/volltexte/2022/16581/). Here I reproduce that footnote in its entirety:
"Briefly, in the notation of [this preprint], it requires that $kn/c < n$, and so $k < c$, but $c$ then takes on all the values of $n, n/2, n/3, \ldots, 1$ and $k \approx \sqrt{n}$. The third author thanks Srikanth Srinivasan [2] who informed him
about this gap in the proof."
