Fourier transform of an arbitrary pair-count operation
ProvedCouret.InterIA.SumAutocorr.dft_pairCountcouret-programmecouret-unification-20261108
Let , , and let be any binary operation on this group. Put . For each ,
The Fourier transform is unnormalized. This identity applies without algebraic assumptions on the operation.
Preamble
import Definitions.Def_Couret_SumAutocorr_074e6f9ba1f0
import Mathlib.Algebra.BigOperators.Group.Finset.Basic
import Mathlib.Algebra.BigOperators.Ring.Finset
import Mathlib.Analysis.Fourier.ZMod
import Mathlib.Data.Finset.Insert
import Mathlib.Data.Finset.Prod
import Mathlib.Data.Finset.SymmDiff
import Mathlib.Data.ZMod.Basic
import Mathlib.Tactic.Abel
import Mathlib.Tactic.NormNum
import Mathlib.Tactic.Ring
import Mathlib.Tactic.Tauto
import Definitions.Def_Couret_ConvolutionParity_aa654fd002fc
import Mathlib.Analysis.Fourier.ZMod
set_option autoImplicit false
namespace Couret.InterIA.SumAutocorr
open Finset Couret.InterIA.Parity
variable {n : ℕ} [NeZero n]
Formal statement
theorem dft_pairCount (S T : Finset (ZMod n))
(op : ZMod n → ZMod n → ZMod n) (k : ZMod n) :
ZMod.dft (fun z => (pairCount S T op z : ℂ)) k =
∑ a ∈ S, ∑ b ∈ T, ZMod.stdAddChar (-(op a b*k)) := by sorry
end Couret.InterIA.SumAutocorr
Source
Alexandre Couret, Couret — Additive reconstruction: STROBO-4, singleton collisions and RECOH formal proof artifacts, https://zenodo.org/records/23980513; archive COURET_MATHEMATIQUES_20261105.zip, SHA-256 19a3b59aee930df74cab79c27b29e014843bd17179a26fef1261ed6b5a651ab7; file source-tree/research/interia/sum-autocorr-20261105/SumAutocorr.lean, lines 31–46; source file SHA-256 034fe0afbe3c002f93196fe2060cea425c9f8cf2da4c42c54bbcf94783bc644d; theorem Couret.InterIA.SumAutocorr.dft_pairCount