#!/usr/bin/env python3 # VERIF_AS_EDGE.py -- verificateur de la note "An edge comparison with constant 3/2 and the coefficient # 6/sqrt(2 pi) for the average sensitivity of polynomial threshold functions" (D. Niedbala Giraudin). # A LANCER EN PYTHON PUR (pas dans Sage). Numpy seul. Aucun argument : bouton Executer. # Ce que le programme verifie (verification des enonces, pas partie des preuves) : # [1] pour des poids w > 0 et des signes h aleatoires, n = 3..7 : les identites (1), (2), (3) de la note, # l'identite exacte de l'etape 3, et l'inegalite |E_h| <= 3/2 ||MH+HM||^2 (lemme 3) ; # [2] le theoreme sur des fonctions a seuil polynomiales aleatoires : AS(f) <= 6 d b_n (n+d)/(n+2d) ; # [3] l'estimation binomiale b_n (n+d)/(n+2d) <= sqrt(n/(2 pi)) en arithmetique exacte pour n <= N_BINOMIAL ; # [4] le temoin rationnel 6/sqrt(2 pi) < 1197/500 en entiers. import itertools, time, math from fractions import Fraction import numpy as np # ============================ REGLAGES ============================ DIMENSIONS = [3, 4, 5, 6, 7] ESSAIS_PAR_DIMENSION = 40 N_BINOMIAL = 2000 GRAINE = 2026 # =================================================================== T0 = time.time() def p(*a): print(*a, flush=True) def cube(n): X = np.array(list(itertools.product([-1, 1], repeat=n)), dtype=float) subsets = sorted([S for k in range(n + 1) for S in itertools.combinations(range(n), k)], key=len) Ch = np.stack([np.prod(X[:, list(S)], axis=1) if S else np.ones(len(X)) for S in subsets], 1) deg = np.array([len(S) for S in subsets]) ham = ((n - X @ X.T) / 2).round().astype(int) idx = {tuple(X[k].astype(int)): k for k in range(len(X))} flip = [np.array([idx[tuple(np.where(np.arange(n) == i, -X[k], X[k]).astype(int))] for k in range(len(X))]) for i in range(n)] return X, Ch, deg, ham, flip, subsets def grading(n, Ch, deg, w): Q, _ = np.linalg.qr(np.sqrt(w)[:, None] * Ch) # Gram-Schmidt dans l'ordre des degres cum = np.r_[0, np.cumsum([np.sum(deg == k) for k in range(n + 1)])] Pi = [Q[:, cum[k]:cum[k + 1]] @ Q[:, cum[k]:cum[k + 1]].T for k in range(n + 1)] M = sum((k - n / 2) * Pi[k] for k in range(n + 1)) return M, Pi def check_lemma(n, X, Ch, deg, ham, flip, w, h): N = len(X); M, Pi = grading(n, Ch, deg, w) err = 0.0 a = [] for i in range(n): Z = np.diag(X[:, i]); Ai = sum(P @ Z @ P for P in Pi) G = Z @ M @ Z - M err = max(err, np.abs(G @ G - (np.eye(N) - Ai @ Ai)).max()) # identite (1) a.append(np.diag(Ai @ Ai)) far_i = (ham >= 2) & (X[:, i][:, None] != X[:, i][None, :]) lhs = 0.25 - M[np.arange(N), flip[i]] ** 2 err = max(err, np.abs(lhs - (a[i] / 4 + np.sum(M ** 2 * far_i, 1))).max()) # identite (2) A0 = np.sum(np.diag(M) ** 2) rhs3 = sum(np.sum(ai) for ai in a) / 4 + np.sum((ham - 1) * (ham >= 2) * M ** 2) err = max(err, abs(A0 - rhs3)) # identite (3) eq = h[:, None] == h[None, :] E = np.sum((ham == 1) & eq) T2 = np.sum((M * (h[:, None] + h[None, :])) ** 2) # identite exacte de l'etape 3 nu = np.zeros((N, N)) for i in range(n): cut = (h != h[flip[i]]).astype(float) nu += (X[:, i][:, None] != X[:, i][None, :]) * cut[:, None] c = nu + nu.T; far = ham >= 2 exact = 4 * (0.5 * np.sum((M ** 2 * (2 - c))[far & ~eq]) - 0.5 * np.sum((M ** 2 * c)[far & eq]) - 0.25 * sum(np.sum(a[i] * (h != h[flip[i]])) for i in range(n))) err = max(err, abs((E - T2) - exact)) return err, E / T2 def bn_exact(n): m = (n - 1) // 2 return Fraction(n * math.comb(n - 1, m), 2 ** n) def autotest(): # poids uniforme : M = -A/2 (adjacence), egalite |E_h| = ||T||^2 X, Ch, deg, ham, flip, _ = cube(3) M, _ = grading(3, Ch, deg, np.ones(8)) ok = np.abs(M + (ham == 1).astype(float) / 2.0).max() < 1e-12 b = [bn_exact(k) for k in (1, 2, 3, 4)] ok = ok and b == [Fraction(1, 2), Fraction(1, 2), Fraction(3, 4), Fraction(3, 4)] p("auto-test (graduation uniforme, b_1..b_4) :", "OK" if ok else "ECHEC") return ok def main(): if not autotest(): return rng = np.random.default_rng(GRAINE) # [1] pire_err, pire_ratio = 0.0, 0.0 for n in DIMENSIONS: X, Ch, deg, ham, flip, _ = cube(n) for t in range(ESSAIS_PAR_DIMENSION): w = np.exp(rng.normal(0, rng.uniform(0, 8), 2 ** n)) h = rng.choice([-1, 1], 2 ** n) e, r = check_lemma(n, X, Ch, deg, ham, flip, w, h) pire_err = max(pire_err, e); pire_ratio = max(pire_ratio, r) p(f"[1] n={n} : {ESSAIS_PAR_DIMENSION} essais, erreur max des identites = {pire_err:.1e}, " f"max |E_h|/||T||^2 = {pire_ratio:.6f} (borne prouvee 1.5) [{time.time()-T0:.0f} s]") # [2] pire_th = 0.0 for n in DIMENSIONS: X, Ch, deg, ham, flip, subsets = cube(n) for d in range(1, n + 1): for t in range(10): coef = rng.normal(size=len(subsets)) * (deg <= d) * (rng.random(len(subsets)) < 0.6) pv = Ch @ coef f = np.where(pv >= 0, 1, -1) AS = sum(np.mean(f != f[flip[i]]) for i in range(n)) b = float(bn_exact(n)) pire_th = max(pire_th, AS / (6 * d * b * (n + d) / (n + 2 * d))) # lemme avec w = |p| (apres perturbation), h = parite * f pv2 = pv.copy() if (pv2 == 0).any(): neg = pv2[pv2 < 0]; pv2 = pv2 + ((min(-neg) / 2) if len(neg) else 1.0) hh = np.prod(X, axis=1) * f e, r = check_lemma(n, X, Ch, deg, ham, flip, np.abs(pv2), hh) pire_err = max(pire_err, e); pire_ratio = max(pire_ratio, r) p(f"[2] n={n} : AS(f) / (6 d b_n (n+d)/(n+2d)) max = {pire_th:.4f} (doit etre <= 1) [{time.time()-T0:.0f} s]") # [3] b_n^2 (n+1)^2 * 2 pi <= n (n+2)^2, avec pi < 355/113 (suffisant) ok3 = True for n in range(1, N_BINOMIAL + 1): b = bn_exact(n) if not (b * b * (n + 1) ** 2 * 2 * Fraction(355, 113) < n * (n + 2) ** 2): ok3 = False; p("[3] ECHEC a n =", n); break p(f"[3] estimation binomiale (cas d = 1, le plus defavorable) verifiee exactement pour n <= {N_BINOMIAL} : " f"{'OK' if ok3 else 'ECHEC'} [{time.time()-T0:.0f} s]") # [4] lb = lambda x: x - x ** 3 / 3 + x ** 5 / 5 - x ** 7 / 7 pi_low = 4 * (lb(Fraction(1, 2)) + lb(Fraction(1, 3))) ok4 = pi_low == Fraction(1538665, 489888) and 18 / pi_low < Fraction(1197, 500) ** 2 p(f"[4] pi > 1538665/489888 et 18/pi < (1197/500)^2 : {'OK' if ok4 else 'ECHEC'}") p("") p("RECAPITULATIF") p(f" identites (1)-(3) et identite exacte de l'etape 3 : erreur max {pire_err:.1e}") p(f" lemme 3 : max observe |E_h|/||T||^2 = {pire_ratio:.6f} <= 1.5 : {'OK' if pire_ratio <= 1.5 + 1e-9 else 'ECHEC'}") p(f" theoreme sur fonctions a seuil aleatoires : {'OK' if pire_th <= 1 + 1e-12 else 'ECHEC'}") p(f" binomial : {'OK' if ok3 else 'ECHEC'} ; temoin rationnel : {'OK' if ok4 else 'ECHEC'}") p(f" duree : {time.time()-T0:.0f} s") if __name__ == "__main__": main() input("Appuyez sur Entree...")