We prove a switching lemma for constant-depth circuits over the alphabet $F_p$ with generalized AND/OR gates, extending Tal's Fourier-analytic approach from the Boolean setting. The key new ingredient is a direct computation of the $L_1$ Fourier mass of AND/OR gates over $F_p$, which yields an exact closed-form expression for the expected high-degree Fourier mass after a random restriction. Combined with a Markov inequality argument, this gives a switching lemma with an explicit, prime-independent structure: $Pr[DT(f|\rho) \geq s] \leq (ep \cdot qK / ((p-1)s))^s$. As a consequence, we obtain that for any prime $p$, constant-depth circuits of sub-exponential size over $F_p$ cannot compute $1[\sum_i x_i \equiv 0 \pmod{p}]$.

Added q<=1/(p-1) technical hypothesis in the improved switching lemma proof; works for the main application since q(surviving prob) usually small. Cleaned up the proof slightly. Should avoid further confusions.

We prove a switching lemma for constant-depth circuits over the alphabet $F_p$ with generalized AND/OR gates, extending Tal's Fourier-analytic approach from the Boolean setting. The key new ingredient is a direct computation of the $L_1$ Fourier mass of AND/OR gates over $F_p$, which yields an exact closed-form expression for the expected high-degree Fourier mass after a random restriction. Combined with a Markov inequality argument, this gives a switching lemma with an explicit, prime-independent structure: $Pr[DT(f|\rho) \geq s] \leq (ep \cdot qK / ((p-1)s))^s$. As a consequence, we obtain that for any prime $p$, constant-depth circuits of sub-exponential size over $F_p$ cannot compute $1[\sum_i x_i \equiv 0 \pmod{p}]$.

Mainly addresses some concerns of Tal:

1. the ambiguity of Depth reduction in Sec 6

2. The bound actually looks stronger?

3. The model is not AC^0[p], but a slightly nonstandard model.

We prove a switching lemma for constant-depth circuits over the alphabet $F_p$ with generalized AND/OR gates, extending Tal's Fourier-analytic approach from the Boolean setting. The key new ingredient is a direct computation of the $L_1$ Fourier mass of AND/OR gates over $F_p$, which yields an exact closed-form expression for the expected high-degree Fourier mass after a random restriction. Combined with a Markov inequality argument, this gives a switching lemma with an explicit, prime-independent structure: $Pr[DT(f|\rho) \geq s] \leq (ep \cdot qK / ((p-1)s))^s$. As a consequence, we obtain that for any prime $p$, constant-depth circuits of sub-exponential size over $F_p$ cannot compute $1[\sum_i x_i \equiv 0 \pmod{p}]$.

Added a note explaining the complementarity of the two switching lemmas: the Fourier paper handles singles gates via Observation 2.4, the CDT handles multi-term formulas via M-independence. Reference will be changed once ECCC version of CDT comes out.

We prove a switching lemma for constant-depth circuits over the alphabet $F_p$ with generalized AND/OR gates, extending Tal's Fourier-analytic approach from the Boolean setting. The key new ingredient is a direct computation of the $L_1$ Fourier mass of AND/OR gates over $F_p$, which yields an exact closed-form expression for the expected high-degree Fourier mass after a random restriction. Combined with a Markov inequality argument, this gives a switching lemma with an explicit, prime-independent structure: $Pr[DT(f|\rho) \geq s] \leq (ep \cdot qK / ((p-1)s))^s$. As a consequence, we obtain that for any prime $p$, constant-depth circuits of sub-exponential size over $F_p$ cannot compute $1[\sum_i x_i \equiv 0 \pmod{p}]$.