g
defimported Lean
$g(S,M) = \dim_{\mathbb{F}_p}(S^{\perp}_M) - \dim_{\mathbb{F}_p}(S_M)$.
Statement
open scoped BigOperators in set_option linter.mathlibStandardSet false in open scoped BigOperators in open scoped Real in open scoped Nat in open Classical in open scoped Pointwise in set_option maxRecDepth 4000 in set_option synthInstance.maxHeartbeats 20000 in set_option synthInstance.maxSize 128 in set_option relaxedAutoImplicit false in set_option autoImplicit false in set_option linter.unnecessarySimpa false in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in noncomputable def g (S : Submodule (F p) (V n p)) (M : Finset (Fin n)) : ℕ
- Defined in
- TCSlib, `g`
- Lean proof
- By Allan Li, Hydroxyi (from the file's git history), from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0. - Verified
- 07 Oct 2026
- Axioms
- none listed
- Built on 4
- S_perp_MThe submodule $S^{\perp}_M = S^{\perp_\omega} \cap V_M$.
- S_MFor a submodule $S \le V$ and $M \subseteq \mathrm{Fin}\,n$, the submodule $S_M = S \cap V_M$.
- VThe ambient space $V = \mathbb{F}_p^n \times \mathbb{F}_p^n$ of pairs of coordinate vectors.
- FThe prime field $\mathrm{GF}(p)$, realized as $\mathbb{Z}/p\mathbb{Z}$ via
ZMod.
- Used by 99
- iterated_round_robin_item_preserving_swaps_zero_of_card_leWhen the number of goods m is at most the number of agents n, for any initial preference profile pref : Fin n → Fin m ≃ Fin m and…
- eefx_bundle_imp_approx_efkLet n ≥ 3 and let σ be an allocation of m goods among n agents with nonnegative additive valuations u such that every agent's bundle is…
- exists_hypercube_coilFor every n ≥ 2, there exists a coil in the hypercube Q_n.
- two_agent_common_bivalued_safe_partitionFor any ratio r with 1 ≤ r ≤ 2, any number of chores m, and any two-agent chore cost profile c satisfying is_scaled_bivalued_chores r c,…
- cleaning_dimension_identityCleaning dimension identity for isotropic subspaces. Let $p$ be prime and let $S \le V = \bbf_p^n \times \bbf_p^n$ be a subspace that is…
- simple_graph_multi_radio_number_path_three_of_le_of_forallReduction of the thread goal to one finite statement per m: if no (m,3)-radio labeling of P_{4m+4} has all labels at most 8m - 2, then the…
- signed_graph_reconstructible_balanced_mono_pair_fixedLet G be a connected balanced signed graph on at least seven vertices, with a specified balance partition. Suppose distinct vertices a and…
- quaternion_odd_has_no_complete_mappingFor every natural number n, the generalized quaternion group QuaternionGroup (2 * n + 1) has no complete mapping.
- three_agent_seven_chores_equal_marginal_sharp_mmsFor three agents, seven chores, any ratio r in [1,2], and any scaled bivalued additive cost profile with common ratio r, there is a…
- simple_graph_triangle_degree_complLet G be an r-regular simple graph on N vertices. For every vertex v, td_{Ḡ}(v) = C(N − r − 1, 2) − N r / 2 + r² − td_G(v), where Ḡ is the…
- condorcet_cubic_subset_potential_residue_barrierFor candidates indexed modulo19, orient a to b when b-a is one of the nine nonzero quadratic residues. Consider any finite family of…
- round_robin_three_agents_pne_not_alpha_ef1_of_three_quarters_ltWith three agents and eight goods, there is an instance with nonnegative additive valuations and a pure Nash equilibrium of Round-Robin…
- p8_reflexive_with_1371_convex_facetsThe 8-dimensional polytope P_8 is a reflexive polytope with exactly 44 vertices and exactly 1371 facets, which exceeds 6^(8/2) = 1296,…
- condorcet_join_cycle_tensor_mixed_fiber_boundFor the fixed19-vertex residue tournament, let left and right real fiber masses lie between0 and a common nonnegative bound k. Assume that…
- is_fractionally_pareto_optimal_scaleMultiplying each agent's additive valuation vector by a positive scale c_i > 0 preserves and reflects fractional Pareto optimality.
- picking_prefix_two_named_first_dev_bundleIn a picking sequence with at most as many turns as goods, suppose agent i acts at turns t1 < t2 and nowhere in between, x is unallocated…
- join_complete_turan_fractional_cover_and_total_weightLet n, r, a be integers with r ≥ 3 and a ≤ n. The edge weighting w_a is a fractional K_r-cover of G_a = K_a ∨ T_{r-1}(n-a), and the total…
- good_slopes_missing_prime_squarefreeLet n be squarefree and nonzero, let the prime p divide n, and let f be a permutation modulo n. Then some residue modulo p is missed by…
- simple_graph_stable_disjoint_edges_outside_packing_incompatible_exampleThere is a stable graph of triangle packing number three, a maximum packing P, and a five-edge triangle cover containing two…
- efx_three_small_goods_obstruction_no_one_natEvery coarse allocation whose first old pair is given to agent 1 fails the conjunction of current utility preservation and the exact…
- hilton_strong_incomparability_matrixFor every natural number n there are a field K, a matrix L over K with rows indexed by the subsets of Fin n and 2^(n-1) columns, and a…
- threshold_schedule_additive_boundFor every horizon T ≥ 2, nonnegative increments a : Fin (T - 1) → NNReal with P runs (P = rent_or_buy_num_runs T a), every positive reset…
- linear_code_supports_rate_cut_boundIf a linear network code over a field F supports the common rate r on net with sessions sess, then for every vertex set S, r times the…
- g_complement_correctableCorrectable erasure and the count of supportable logical operators. Let $S$ be an isotropic subspace of the symplectic space…
- not_is_pk_free_claw_free_hole_dominatingThe statement
is_pk_free_claw_free_hole_dominatingis false: The statement is false as written: it allows k = 4 and m = 3 (since k - 1 =… - condorcet_selector_closed_candidates_global_coreConsider uniquely indexed three-candidate committees S(i), each with an outside root f(i), and the claim relation R(i,j) iff f(j) belongs…
- op223_local_principal_maxima_not_sufficientThere is a tree on exactly three vertices with an edge uv that can be replaced by a nonedge so that the result remains a tree and has…
- balanced_high_count_chore_mms_boundFor n at least two, k at least two and n*k bivalued chores, a bundle of size k whose high-cost count times n is at most the total…
- wild_number_complete_graph_279_min_proper_coloring_eqNew case of OP-306: every minimum proper edge colouring of K_279 has wild number 186 = floor(4*ceil(279/2)/3). The lower bound is the…
- simple_graph_cycle_power_seven_layer_weight_leLet n ≥ 22 and let c label the vertices of C_n^7 so that every label class is a clique. Then Σ_i (2·[i ~ i+7] + [i ~ i+6] + [i ~ i+4]) ≤…
- round_robin_runs_coincide_bundle_eqIf two Round-Robin executions have the same set of allocated items at each turn s <= m, then both executions produce identical final…
- third_principal_specialization_congrIf two finite graphs are isomorphic, their third principal specializations are equal as bivariate polynomials.
- correctable_implies_g_zeroCorrectable coordinate sets carry no supportable logical operators. Fix a prime $p$, let $V = \bbf_p^n \times \bbf_p^n$ be equipped with…
- cycle_power_eight_corrected_count_upper_windowIn every zero-phase defective half model of exponent three, the corrected lower count at v is at least its value at v+4.
- picking_phi_entry_leFor the Round-Robin sequence of n agents and m goods, the 0-based rank phi_s of the item selected at turn s is at most s (the paper's 1 <=…
- not_planar_all_powers_well_covered_characterizationIt is not the case that every finite connected simple planar graph G with at least two vertices whose powers G^d are all well-covered is…
- petrial_R_is_treeFor every natural number m, the graph R_m is a tree.
- subcubic_rich_neighbor_five_isolated_vertex_extendIf v is an isolated vertex of the finite simple graph G and the induced subgraph of G on the vertices other than v admits a rich-neighbor…
- op223_nonsustainable_tree_fin_fourEvery non-sustainable tree on four vertices is isomorphic to the star graph K_{1,3}.
- stein_param_inj_onThe map sending (d, u, v) to d^2 * (u^4 + 4 * v^4) is injective on stein_param_set.
- cycle_power_eight_corrected_count_lower_windowIn every zero-phase defective half model of exponent three, the corrected lower count at v is at most its value at v+4.
- condorcet_reversal_tensor_acyclic_half_cover_iffLet R be any directed relation on Fin m, let n be any natural number, and suppose a map tau on Fin m reverses every R-arrow. The relation…
- op223_no_nonsustainable_tree_fin_threeThere are no non-sustainable trees on three vertices.
- bibd_isomorphic_of_block_clique_graph_isoOP-1148: if two BIBDs D₁, D₂ with the same parameters (v, b, r, k, λ) on finite block sets have isomorphic modified block-clique graphs…
- ternary_lift_realApproxDegree_leSuppose n, d : ℕ with 40 ≤ n. If f : (Fin n → Bool) → Bool, P : (Fin n → Bool) → ℝ is in degreeSpace ℝ (Fin n) d, and Z : (Fin n → Bool) →…
- slow_mode_dephasing_zeroAt time s = 0, the quantum slow-mode dephasing factor kappa_{n,m}(0) equals 1 for every n >= 2 and every m.
- unit_incidence_matrix_isTotallyUnimodularEvery square minor of a matrix whose rows are differences of standard basis vectors e_{u i} - e_{v i} is 0, 1 or -1 (Mathlib: the matrix…
- wild_triple_partition_mass_le_of_odd_ge_179For every odd number q of triple blocks with q>=179, the existing sufficient canonical seal-event resource sum wtc_mass(q) is at most1/50.…
- greedy_matching_fraction_ge_of_blocking_leLet P be a hereditary segment property. If β_P(ℓ) ≤ p (formalized by segment_blocking_bound_le P ℓ p), then on every duplicate-free list…
- not_cop_win_two_of_dominating_cycleThe statement
cop_win_two_of_dominating_cycleis false: The theorem is FALSE. A concrete counterexample is the Petersen graph P on 10… - simple_graph_lex_cover_private_triangle_not_extendable_exampleThere is a stable graph with triangle packing number two, a maximum packing P, and a minimum triangle cover C minimizing its edges outside…
- exists_submodular_instance_no_ef1_envy_freeable_allocation_with_bobw_lotteryThere is an instance with three agents and four indivisible goods, each agent having a normalized monotone submodular valuation, in which…
- g_expansionExpansion of the operator count $g(S,M)$. Fix a prime $p$ and equip $V = \bbf_p^{\,n} \times \bbf_p^{\,n}$ with the symplectic form…
- wild_triple_partition_mass_criterionFor an odd number q of triple blocks, q>=3, a proper edge coloring of K_(3q) with 3q colors and a bijection between colors and their…
- picking_prefix_state_alloc_card_eqAfter s turns of a picking sequence with at most as many turns as goods, exactly min s (length seq) goods have been allocated (in…
- hermitian_matrix_parseval_sumFor any natural number d ≥ 1, any orthonormal Hermitian basis T of trace-zero matrices, and any Hermitian matrix A, the sum of squared…
- condorcet_dimension_le_three_iff_acyclic_weight_separationThe following two universal statements are equivalent. First, every finite election with a positive number of voters and strict rankings…
- hypercube_max_coil_disjoint_squares_posFor n ≥ 13, if S is a maximum coil in Q_n with degree count y_0 > 0, then the number F_5 of squares disjoint from S is strictly positive.
- bibd_isomorphic_of_block_clique_graph_iso_of_three_leRecoverability of a BIBD from its modified block-clique graph when the block size k is at least 3: if two BIBDs D₁, D₂ with the same…
- seeded_subtraction_seq_eventually_periodicFor every integer $a \ge 1$ and every binary initial seed of length $2a + 1$, the generated subtraction sequence is eventually periodic.
- sumset_rep_count_le_choose_mul_chooseFor any k ≥ 1, h, q, and integer s, the representation count ν_q(s) is bounded above by (h + k choose k - 1) * (q choose k - 1).
- op_1004_two_type_efx_fpo_single_typeFor two agents and any finite set of identical goods valued at c > 0 by agent 0 and d > 0 by agent 1, there exists an allocation that is…
- wild_partition_large_order_resource_boundsSuppose n is odd, q>=10000000, 3q<=n<=3q+2, and a proper n-coloring of K_n has a bijection between colors and their unique missing…
- op_1534_constant_word_deletion_envelope_eqFor integers t ≥ 1, q ≥ 2, and n ≥ 1, and any threshold r, the t-deletion hinge sum of the all-zero word qary_all_zero_word q n (by omega)…
- xz_rho_trace_oneFor every natural number L with 1 ≤ L, the trace of the reduced density matrix
xz_rho Lequals 1:Matrix.trace (xz_rho L) = 1. - round_robin_pne_ef1_of_card_le_two_mulWith n agents and at most 2n goods (every agent picks at most twice), every pure Nash equilibrium of Round-Robin, for nonnegative additive…
- op_193_k3_m10_at_least_85_verticesThe stable triple graph of the ten-cycle plus an isolated vertex has at least 85 vertices.
- tarski_box_query_le_succ_halvingOne dimension costs a factor log₂ n: from a box-search algorithm in dimension k with q queries one gets one in dimension k+1 with at most…
- quantitative_combinatorial_nullstellensatzFor a multivariate polynomial f of total degree at most ∑ t_i over a field F, the coefficient of the monomial ∏ x_i^{t_i} equals the sum…
- g_add_dimsAdditive dimension identity for an isotropic subspace. Let $S$ be an isotropic submodule of the symplectic space…
- exists_physical_pairs_bijectiveLet L be a 2l-dimensional submodule of V k 2 over F 2 that is nondegenerate under the symplectic bilinear form symB. Then there exists a…
- g_le_two_card_CCorrectable part contributes nothing to the operator count. Let $p$ be prime and let $S$ be an $\mathbb{F}_p$-subspace of the symplectic…
- simple_graph_cycle_power_three_layer_weight_leLet n ≥ 10 and let c label the vertices of C_n^3 so that every label class is a clique. Then Σ_i (2·[i and i+3 share a class] + [i and i+2…
- graph_edit_cost_permutation_decomposition_le_two_mulLet $Q$ be an $n \times n$ doubly stochastic matrix with a convex decomposition $Q = \sum_{i \in \iota} w_i P_{\pi_i}$, where $w_i \ge 0$,…
- wild_valid_triples_nine_factorEvery injective nine-vertex restriction of a normalized symmetric row-injective array can be permuted into three valid triples. The range…
- ndeg_le_nFor any natural number n and any Boolean function f : (Fin n → Bool) → Bool, the non-deterministic degree of f is at most n.
- simple_graph_multi_radio_number_path_monoThe (m,k)-radio number of the path P_n is nondecreasing in n: a labeling of P_{n+1} restricts to one of P_n.
- op223_tree_fin_four_iso_path_or_starEvery tree on four vertices is isomorphic either to the path graph on four vertices or to the star K_{1,3}.
- recursively_balanced_alpha_le_round_robin_universal_alphaThe universal EF1 approximation factor for recursively balanced sequences recursively_balanced_alpha is at most the universal factor for…
- mst_id_certificate_imp_minor_edges_loop_or_bridgeIf a partial realization β is an MST identification certificate for a connected simple graph G on a finite vertex set, then every…
- lex_stream_order_embedding_of_intervalsGiven a family of strictly separated intervals [l(a), r(a)] in (0, 1/2], the Cantor-type series Φ(u) = ∑_{k=0}^∞ (∏_{j<k} (r(u(j)) -…
- bipartite_subset_colorable_succFor every positive k and threshold r, colorability of the standard-list subset graph at k implies colorability at k+1 and the same…
- picking_prefix_state_alloc_monoThe set of allocated goods is monotone in the number of turns: if s <= t then the goods allocated after s turns are allocated after t turns.
- fourier_threshold_nu_odd_ge_arithmetic_boundFor every integer m >= 1, the arithmetic bound lambda_{2m+1} is a lower bound on the Fourier threshold nu(2m+1).
- vertex_cover_num_le_two_mul_matching_numIn any finite simple graph G, the vertex cover number is at most twice the matching number: G.vertexCoverNum ≤ 2 * graph_matching_num G.
- g_formulaDimension formula for the operator count of an isotropic subspace. Let $p$ be prime, and equip the symplectic space…
- op_1710_kuramoto_coupling_iso_eqFor any two isomorphic graphs T and T' on a finite vertex set V, any probability measure μ on ℝ, and any threshold s, the probability that…
- signed_graph_reconstructible_balanced_three_fixedEvery connected balanced signed graph on at least seven vertices is reconstructible from its switching deck if its underlying graph has…
- round_robin_divergence_turn_actorIf only agent i deviates and the executions have identical allocated sets up to turn t but diverge at turn t + 1, then the agent acting at…
- round_robin_pne_not_ef1_three_agents_eight_goodsThere is an instance with 3 agents, 8 goods and strictly positive additive valuations, and a pure Nash equilibrium of the Round-Robin…
- two_disjoint_correctable_sets_bound_logical_dimensionTwo disjoint correctable erasures bound the logical dimension. Work in the symplectic space $V = \bbf_p^{\,n} \times \bbf_p^{\,n}$ over…
- odd_antihole_colorable_of_common_paletteTheorem 8 of arXiv:2610.14241 for the odd antihole: for ℓ ≥ 3, if all lists of an (ℓ-1)-assignment of complement(C_{2ℓ-1}) are subsets of…
- three_agent_critical_equal_weight_allocation_familyFor three agents and seven chores, suppose each agent designates four chores high. There exist three allocations such that every chore…
- simple_graph_stable_triangle_active_edge_in_maximum_packingIn a finite graph where deleting any edge preserves the maximum triangle packing number, every edge belonging to a triangle is used by…
- k_submod_c1_hidden_fn_orthant_diminishing_returnsFor all natural numbers n > 0 and k ≥ 2, every hidden assignment σ : Fin n → Fin k, and every function H : ℝ → ℝ → ℝ satisfying…
- hamming_norm_monomialFor any natural number s and any finite subset T of Fin s, the Hamming norm of the coordinate monomial monomial T as a function from (Fin…
- maxcut_anchor_three_initial_optimalThe displayed initial coloring sigma of the 91-vertex graph G_3 in arXiv:2610.04948 maximizes social welfare among all three-colorings.
- signed_graph_reconstructible_balanced_mixed_twin_pairLet G be a connected balanced signed graph on at least five vertices, with a specified balance partition. Suppose distinct vertices a and…
- condorcet_coherent_clone_uniform_half_obstructionSuppose a root selector on m candidates is invariant under input permutations and the two multiplicity patterns of a two-candidate sample,…
Lean source view module on GitHub
open scoped BigOperators in set_option linter.mathlibStandardSet false in open scoped BigOperators in open scoped Real in open scoped Nat in open Classical in open scoped Pointwise in set_option maxRecDepth 4000 in set_option synthInstance.maxHeartbeats 20000 in set_option synthInstance.maxSize 128 in set_option relaxedAutoImplicit false in set_option autoImplicit false in set_option linter.unnecessarySimpa false in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in variable {n : ℕ} {p : ℕ} [Fact p.Prime] in /-- Supportable logical operators count g(M) -/ noncomputable def g (S : Submodule (F p) (V n p)) (M : Finset (Fin n)) : ℕ := Module.finrank (F p) (S_perp_M S M) - Module.finrank (F p) (S_M S M) /- Checking FiniteDimensional instances. -/