symmetric_counterexample_func
For any integer n, the symmetric Boolean function F_n on (Fin n → ZMod 2) is the sum over j from 0 to n / 4 of the elementary symmetric Boolean polynomial of degree 2j, where σ_{2j}(x) is the sum over subsets s of Fin n of size 2j of the product of coordinates in s.
Statement
def symmetric_counterexample_func (n : ℕ) (x : Fin n → ZMod 2) : ZMod 2- Defined in
- arXiv:2611.06744, Theorem 1
- Verified
- 09 Nov 2026
- Axioms
- none listed
- Used by 3
- symmetric_counterexample_support_weight_iffFor any n = 2^k ≥ 8 and any input v : Fin n → ZMod 2, the symmetric Boolean function symmetric_counterexample_func n evaluates to 1 on v…
- symmetric_counterexample_func_eight_eqThe symmetric Boolean function symmetric_counterexample_func 8 on (Fin 8 → ZMod 2) equals symmetric_counterexample_func_eight.
- symmetric_counterexample_func_ne_zeroFor every natural number n, the symmetric Boolean function symmetric_counterexample_func n is not identically zero.
Read back from the Lean
A definition of symmetric_counterexample_func, which takes a natural number n and a function x : Fin n → ZMod 2, and returns the element of ZMod 2 given by:
$$\sum_{j = 0}^{\lfloor n / 4 \rfloor} \sum_{\substack{s \subseteq \mathrm{Fin}\, n \\ |s| = 2j}} \prod_{i \in s} x(i)$$
that is, the sum in $\mathbb{Z}/2\mathbb{Z}$ of the elementary symmetric polynomials of even degree $2j$, for $0 \le j \le \lfloor n/4 \rfloor$, evaluated on $x$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The symmetric Boolean function F_n = ∑_{j=0}^{n/4} σ_{2j} on (Fin n → ZMod 2). -/ def symmetric_counterexample_func (n : ℕ) (x : Fin n → ZMod 2) : ZMod 2 := ∑ j ∈ Finset.range (n / 4 + 1), ∑ s ∈ Finset.powersetCard (2 * j) Finset.univ, ∏ i ∈ s, x i