TotalPreorder
classimported Lean
A total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or decidable equality. Two distinct elements can be indifferent. This is the appropriate notion for weak preferences in utility theory and matching theory. [MSZ 2.1–2.4]
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in class TotalPreorder (A : Type*) extends Preorder A
- Defined in
- EconCSLib, `TotalPreorder`
- Lean proof
- By xbei (from the file's git history), from github.com/gametheoryinlean/EconCSLib at
1a88f809b538(Copyright (c) 2026 EconCSLib contributors. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.30.0.TotalPreorder← TotalPreorder (EconCSLib/Foundation/Preference.lean:117): verbatim
- Verified
- 08 Oct 2026
- Axioms
- none listed
- Used by 755
- GameTree.value_LeafGameTree.value_Leaf
- op75_final_encoding_templateThe final target layer encoding is a fixed prefix followed by the negative and positive target coefficient encodings.
- cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core_b00000One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core: under the layer-free tight-cover…
- chore_residual_cost_of_card_leGiven a type α with decidable equality, a cost function c : α → NNReal, a natural number k : ℕ, and a bundle S : Finset α with S.card ≤ k,…
- nat_sum_lt_of_subset_square_mod_ltIf all summands are below n and every subset sum has residue below n modulo n squared, then their total is below n.
- postage_stamp_number_neg_two_of_odd_dvd_eqIf 0 < N, N ∣ D and 0 < D < 2N, then D = N.
- postage_stamp_number_neg_two_of_odd_family_eFor h = 12r+5 (m = 6r+2), the set {-(2r+1), 2r+1, 4r+4} h-fold covers [0, 36r² + 48r + 12] = [0, n_h(2) - 2].
- single_peaked_median_is_condorcet_winnerUnder single-peaked preferences with asymmetric preferences, if an alternative m satisfies that strictly more than half of the voters have…
- cycle_power_fifteen_tight_type_sequence_six_iff_seven_core_b110One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_six_iff_seven_core: under the layer-free tight-cover…
- GameTree.Kuhn_exists_SPE_onKuhn's theorem, root-scoped SPE form: every finite perfect-information game without chance has a pure strategy that is subgame-perfect…
- KnapsackAuction.binaryToAllocation_fractionalFeasible_of_binaryRespectsCapacityKnapsackAuction.binaryToAllocation_fractionalFeasible_of_binaryRespectsCapacity
- cycle_power_fifteen_tight_type_sequence_ten_iff_eleven_core_b010One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_ten_iff_eleven_core: under the layer-free tight-cover…
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_a01001One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- card_filter_subset_le_sum_card_filter_insertLet α be a type with decidable equality. Let ℱ be a finite family of finite subsets of α such that for all F1, F2 ∈ ℱ, the intersection F1…
- GameTree.value_Node_eq_some_child_valueThe value at a node is itself the value of some child (the argmax). Specifically,
argMaxOn ... ∈ value h :: valueList t, so it equals… - is_rank_three_signotopeA function u : OrderedTriple α → ℤˣ assigning units of ℤ ({+1, -1}) to ordered triples in a linearly ordered type α is a rank-3 signotope…
- cycle_power_fifteen_tight_type_sequence_four_iff_five_core_a001One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_four_iff_five_core: under the layer-free tight-cover…
- forest_greedy_threshold_event_countFor two finite uniform endpoint populations and a fair tie coin, the number of greedy updates reaching an integer threshold is bounded by…
- cycle_power_fifteen_tight_type_sequence_one_alternates_core_alt000100One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_alternates_core: under the layer-free tight-cover…
- condorcet_crossed_uniform_family_incidence_boundFor a nonempty r-uniform family F, a set A that is empty or crosses a member of F, and a subfamily B disjoint from A, let Z be the number…
- GameTree.value_NodeGameTree.value_Node
- cycle_power_fifteen_tight_type_sequence_six_iff_seven_core_a111110One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_six_iff_seven_core: under the layer-free tight-cover…
- finite_two_incidence_capacity_assignmentA finite incidence relation with two endpoints for every edge and at most d incident edges at every vertex, d at least two, admits an…
- wild_normalized_array_six_seal_second_factorial_boundFor every normalized symmetric idempotent row-injective array on Fin n, let mu(S) count colors outside a six-set S whose matching edges…
- VNM.IndependenceIndependence: mixing both sides with a common lottery preserves preference.
L₁ ≿ L₂ ↔ [α L₁, (1-α) N] ≿ [α L₂, (1-α) N]forα > 0. - countable_lex_stream_order_embedding_existsEvery lexicographic stream space over a countable linearly ordered alphabet admits an order embedding into the real line.
- op_193_cubic_cycle_anchor_avoidanceOn any cycle of length at least k times ((k-1)^2+1), every family of m-2k+2 subsets of size at most k admits a stable k-set meeting each…
- IsCompact.continuous_iSupIsCompact.continuous_iSup
- card_candidate_links_le_sqFor every natural number n and every finite set L of pairs of integers (i, j) satisfying 0 ≤ i < j < n, the cardinality of L is at most n…
- op_258_has_mono_clique_of_bounded_colorsFor any clique size k ≥ 1 and colour bound C ≥ 1, there exists N such that for all n ≥ N, every edge colouring of K_n with colors at most…
- Matrix.blockTriangular.powPowers of block triangular matrices are block triangular.
- cycle_power_fifteen_tight_type_sequence_one_alternates_core_alt001One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_alternates_core: under the layer-free tight-cover…
- cake_allocation_uses_at_most_cutsAn allocation of the cake [0, 1] among n agents with bundles C : Fin n → Set ℝ uses at most q cuts if there exist an integer k ≤ q and a…
- singularValuesSorted_antitoneSorted singular values are antitone (decreasing).
- op_153_positive_quadratic_sublevel_card_boundFor a degree-2 integer polynomial strictly positive on positive integers, the number of positive integers $n \le N$ with $g(n) \le N$ is…
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_a000000One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- wild_triple_partition_term_geometric_tailFor q>=3 odd and any h>=5 with2*h<=q, the existing canonical triple-partition resource term wtc_term(q,h) is at most 3*h*(27/40)^h. The…
- mondrian_two_chain_prefix_boundIf p is greater than r plus one, then (r+1) times the sum of p^i for i below a is strictly smaller than p^a.
- comparison_tree_selects_rank_existsFor every n and every rank r : Fin n there exists a comparison decision tree on n elements that correctly selects the element of rank r.
- mondrian_no_perfect_sixThe integer square of side six has no perfect admissible partition.
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_a000011000010One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- GameTree.IsSubgamePerfectOnRoot-scoped subgame perfection on the subtrees of a fixed root.
IsSubgamePerfect σis global over everyGameTree N U. This predicate… - SocialChoice.Voting.topRank_eq_topChoiceSocialChoice.Voting.topRank_eq_topChoice
- KnapsackAuction.welfareMaximizerKnapsackAuction.welfareMaximizer
- cycle_power_fifteen_tight_type_sequence_ten_iff_eleven_core_b00111One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_ten_iff_eleven_core: under the layer-free tight-cover…
- Fin.succSuccAbove_monotoneFin.succSuccAbove_monotone
- Fin.succSuccAbove_symmFin.succSuccAbove_symm
- simple_graph_path_radio_labeling_four_mul_add_threeFor m >= 1, the labeling of the path P_{4m+3} that gives an odd vertex v the labels v, v+4, ..., v+4(m-1) and an even vertex v the labels…
- IsCompact.continuous_iInfIsCompact.continuous_iInf
- mondrian_twice_exponent_lt_prime_powerFor p at least two and r at least three, p^r is greater than twice r.
- Fin.succSuccAbove_strictMonoFin.succSuccAbove_strictMono
- 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…
- tarski_slice_lower_boundMonotonicity preservation on coordinate slices: fixing coordinate i to any value m ≥ a_i preserves the lower subinterval invariant a_j ≤…
- ejr_chain_exists_of_support_density_boundA permutation whose every prefix satisfies the proposed density bound yields an EJR committee chain.
- observable_upper_bound_base_polytopeFor any vector a whose values are sorted non-decreasingly by permutation π, and any point z in the base polytope of C, the inner product ∑…
- tarski_fixed_point_existsEvery monotone self-map on the discrete grid [n]^k possesses at least one fixed point, by Tarski's fixed point theorem on finite complete…
- cycle_power_fifteen_tight_type_sequence_shape_rules_core_v121_130Window refutation for k = 15: in the layer-free tight-class model on the integer line (x p j: the class starting at p contains p + j;…
- cycle_power_fifteen_tight_type_sequence_four_iff_five_core_a111One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_four_iff_five_core: under the layer-free tight-cover…
- exists_radio_labeling_top_span_eqUpper bound: the labeling f(v_i) = {ik, (n+i)k, ..., ((m-1)n+i)k} is an (m,k)-radio labeling of K_n of span k(mn - 1).
- two_ray_nonnegative_sum_strict_boundUnder the same weighted two-ray relation, with D and a positive, a+b at most D, B nonnegative, the coordinate sum of u strictly less than…
- is_m_interval_posetAn m-interval-poset of size n is an interval-poset on Fin (n * m) where within each block of size m, the elements are ordered in…
- triangle_reduction_clique_counting_obstructionThe displayed natural-number inequalities for the four types of packed triangles, cover size, and uncovered cross edges are inconsistent…
- not_edge_connectivity_ge_half_scale_mul_min_degree_mul_lly_lower_boundThe inequality κ'(G) ≥ (d/2) δ(G) κ_LLY^(d)(G) asked in OP-164 fails for d = 4: take a 4-cycle 0–1–2–3–0 and a triangle 4–5–6 joined by…
- dedekind_numberThe n-th Dedekind number d_n is the number of monotone Boolean functions on n variables, defined as the cardinality of the poset of…
- forward_biased_selector_output_uniqueFor any cache C, hitting probabilities α, and target page e, if μ₁ and μ₂ both satisfy is_forward_biased_selector_output C α e, then μ₁ =…
- coordinate_orbit_invariant_orderhom_isoFor a subgroup of coordinate permutations of the n-fold product of the finite chain Fin m and a partially ordered set T, the pointwise…
- cycle_power_dyadic_central_position_existsIn a periodic tight dyadic class model with exact dyadic coverage and coverage at all lower neighbour distances, some class uses one of…
- is_lap_trace_minimalA graph G on a finite vertex set V is Laplacian trace-minimal in the class of d-regular graphs if G is d-regular and its Laplacian trace…
- GameTree.outcome_LeafGameTree.outcome_Leaf
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_b0001One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- cycle_power_fifteen_tight_type_sequence_two_iff_three_core_a101One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_two_iff_three_core: under the layer-free tight-cover…
- cycle_power_fifteen_tight_type_sequence_ten_iff_eleven_core_b011One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_ten_iff_eleven_core: under the layer-free tight-cover…
- op_686_single_element_admissibleFor all natural numbers k, m : ℕ satisfying 2 ≤ k and k < m, the single-element set {(k, m)} is an admissible inflection set…
- IsCompact.sInf_image_eq_sInf_image_closureIsCompact.sInf_image_eq_sInf_image_closure
- cycle_power_fifteen_tight_type_sequence_six_iff_seven_core_b01One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_six_iff_seven_core: under the layer-free tight-cover…
- LownerHeinzCore.cfcₙ_rpowIntegrand₀₁_eq_smul_cfcR_ratioLownerHeinzCore.cfcₙ_rpowIntegrand₀₁_eq_smul_cfcR_ratio
- GameTree.IVariant.refl
IVariantis reflexive: any strategy is ani-variant of itself. - ordered_biclique_minimum_incidence_intervalsLet g be positive and take g-1 bicliques indexed by cuts r+1 of the ordered set Fin g, with the first side strictly above r and the second…
- cycle_power_fifteen_tight_type_sequence_six_iff_seven_core_b111One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_six_iff_seven_core: under the layer-free tight-cover…
- mondrian_large_prime_descentIf c is positive and p is a prime greater than c, any perfect partition of the c times p to the e square yields a perfect partition of the…
- cycle_power_fifteen_tight_type_sequence_two_iff_three_core_a1101One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_two_iff_three_core: under the layer-free tight-cover…
- pandora_exists_deadline_orderLemma 2: a deadline-feasible set can be listed without repetition so that the j-th box (j from 1) has deadline at least j.
- simple_graph_cycle_power_clique_arcFor n at least 3k+1, every nonempty clique of the k-th cycle power lies in a forward arc of k+1 vertices whose first vertex belongs to the…
- probabilistic_serial_fractional_assignment_two_same_oneTwo agents who both rank item 1 first each get half of each item under probabilistic serial.
- cycle_power_fifteen_tight_type_sequence_four_iff_five_core_a00011One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_four_iff_five_core: under the layer-free tight-cover…
- ContinuousLinearMap.continuous_iSupA specialization of
Bornology.IsBounded.continuous_iSup_bilineartoContinuousLinearMap. - KnapsackAuction.binaryRespectsCapacityCapacity feasibility for a binary allocation profile.
- graph_lly_curvature_of_leafIf x is a leaf of a finite connected graph whose only neighbour is y, then κ_LLY(x, y) = 2/d_y.
- IsPositiveAffineOf.transPositive affine transformation is transitive.
- GameTree.Kuhn_exists_NEKuhn's theorem, NE form: every finite perfect-information game without chance has a pure-strategy Nash equilibrium.
- op_258_exists_finset_sum_gt_oneIf f : α → ℝ is nonnegative and its ENNReal-sum of ENNReal.ofReal (f ·) is strictly greater than 1, then some finite set I of indices and…
- postage_stamp_basis_mem_h_fold_sumset_mod_twelve_eq_nineFor any r : ℕ and any m ≤ 36r² + 72r + 33, m belongs to the (12r+9)-fold sumset of {-(2r+2), 2r+2, 4r+5}.
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_b000011One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- seidel_matrix_compl_codegree_eqFor any simple graph G on a finite vertex set V with Seidel matrix S and any pair of adjacent vertices u and v in the complement Gᶜ, four…
- scalar_sampler_integrality_of_modEqIf an integer B satisfies B ≡ -m_j * A (mod m_j^2) with m_j ≠ 0, then A / m_j + B / m_j^2 is an integer.
- ido_opposite_pair_cost_le_four_thirdsIn an identically ordered instance of m chores and n agents with 2 * n ≤ m and nonnegative costs c where every agent has maximin share 1,…
- Fin.succSuccAbove_injectiveFin.succSuccAbove_injective
- simple_graph_equivalence_covering_number_cycle_power_large_upperFor every natural k at least one and natural n at least max(2*k+2, twice the square of k), the equivalence covering number of the k-th…
- op869_orient_pairs_halfGiven finitely many marked pairs of distinct indices, there is a set of indices whose boundary crosses at least half the pairs, counting…
- cycle_power_fifteen_tight_type_sequence_six_iff_seven_core_b0000000One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_six_iff_seven_core: under the layer-free tight-cover…
- cycle_power_fifteen_tight_type_sequence_two_iff_three_core_a10001One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_two_iff_three_core: under the layer-free tight-cover…
- sumset_rep_countFor natural numbers h, k, q and integer s, sumset_rep_count h k q s is the number of pairs (x, A) in (sumset_sum_vectors_finset (h + 1) k)…
- prioritized_borel_eventual_hidden_shadowCompatible finite histories whose hidden-choice records eventually do not increase and whose extensions add no hidden choices eventually…
- TensorSpecies.Tensor.IsReindexing.succAbove_succSuccAbove_commRemoving one entry and then a pair of entries from
cin either order gives the same colour list: removing thek-th entry and then the… - op_517_zero_excess_of_eq_pairFor any instance inst of WiringDiagramPair, if the two signotopes inst.u and inst.v are equal, then inst has braid-move excess 0…
- probabilistic_serial_line_distortion_ge_sharpSharpness half of OP-1158: for every n >= 2 and every real c < n there are n agents and n items at real positions with positive minimum…
- op_153_positive_quadratic_eventually_quadratic_lower_boundA degree-2 integer polynomial strictly positive on positive integers satisfies $n^2 \le 2 g(n)$ for all sufficiently large positive…
- simple_graph_complete_no_small_vertex_triangle_reductionIn a complete graph, a nonempty vertex set of size at most one forty-first of the order cannot satisfy the standard vertex packing-cover…
- 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,…
- integer_positive_line_boundary_indicesFor finite integer functions x,w with x strictly positive coordinatewise and w taking both positive and negative values, there are indices…
- cross_cut_card_ge_minDegree_of_diam_twoPlesník's cut lemma: in a finite connected graph G with diam(G) = 2, every nontrivial vertex cut (A, Aᶜ) has at least δ(G) crossing edges.
- is_ultrametric_transitionFor a natural number n and a linearly ordered type α, an n-by-n matrix P : Matrix (Fin n) (Fin n) α satisfies the ultrametric transition…
- three_deletion_num_embeddingsFor a binary word w of length n and a binary word y of length n + 3, three_deletion_num_embeddings n w y is the number of strictly…
- galvin_bipartite_multigraph_list_edge_colouring_twoThe k = 2 case of Galvin's list edge colouring theorem in fibre form: if every fibre of f and every fibre of g has at most two elements…
- simple_graph_two_edge_stable_connected_family_exchange_trap_counterexampleThere is a connected 18-vertex graph with 57 edges, packing number 14, all edge pairs avoidable by maximum packings, at least three…
- digraph_weighted_in_degree_below_halfIn a finite nonempty oriented graph, some vertex minimizes the weight of its in-neighborhood, and that in-neighborhood has at most half…
- ghz_matching_index_le_min_degreeFor any finite type V with decidable equality and any connected simple graph G on V with decidable adjacency, the matching index…
- Bornology.IsBounded.continuous_sSupBornology.IsBounded.continuous_sSup
- zero_sum_basis_seq_w_badFor n > 1 and r ≥ 1, the admissible sequence E_{r,n} (length 2r(n−1)) has no nonempty subsequence whose sum is ≡ 0 (mod n) but ≢ 0 (mod n²).
- zero_sum_w_two_leUpper bound w_r(2) <= 2r + 1: every sequence of 2r + 1 vectors of Z^r, each nonzero mod 2, has a nonempty subsequence whose sum is 0 mod 2…
- Dimension.Exponent.coe_le_coeDimension.Exponent.coe_le_coe
- cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core_a11One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core: under the layer-free tight-cover…
- CommunicationComplexity.Internal.uniformApprox_approxUniform approximation error bound. Let $p$ be a probability mass function on $\mathrm{Fin}\,m$ with $m \ge 1$, and let $n \ge 1$ be an…
- condorcet_failure_iff_acyclic_half_coverFix a positive number n of voters. There exists a finite election with these n voters in which every candidate set of size at most three…
- postage_stamp_number_neg_two_of_odd_upper_threeFor odd h ≥ 5 with h ≡ 11 (mod 12), every 3-element set with a negative element has h-range at most n_h(2) - 3.
- IsCompact.sSup_image_eq_sSup_image_closureIsCompact.sSup_image_eq_sSup_image_closure
- admissible_card_le_nat_sqrtIf A is a nonempty admissible subset of {1, ..., N}, then the cardinality of A is at most the integer square root of 6 times N.
- mixed_radix_offset_bijectiveFor any table size n ≥ 2 and any permutation P of the prime factors of n, the mixed-radix reversed offset sequence mixed_radix_offset n P…
- SocialChoice.FairDivision.Divisible.cutter_isEnvyFree_of_fairThe cutter (agent 0) does not envy the chooser at a fair cut. If the cut point
tsatisfiesIsFairCutPoint μ t, then agent 0 values… - cycle_power_fifteen_tight_type_sequence_ten_iff_eleven_core_b0010One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_ten_iff_eleven_core: under the layer-free tight-cover…
- tarski_subinterval_slice_shrinkSlicing contraction principle: if x is a fixed point of f on all coordinates j ≠ i within [a, b], then comparing f(x)_i with x_i either…
- simple_graph_has_equivalence_cover_cycle_power_large_upperFor natural k at least one and n at least max(2k+2,twice the square of k), the k-th cycle power on n vertices has an equivalence cover…
- TotalPreorder.comparableIn a total preorder, any two elements are comparable.
- four_point_positive_kernel_mixed_directionLet a,b be two integer rows on four coordinates and x a strictly positive integer vector annihilated by both rows. If the first two…
- davenport_box_three_even_sequence_sumThe sequence T(m) (even case) is a zero-sum sequence, for every m ≥ 2.
- SocialChoice.Voting.rank_lt_of_ltSocialChoice.Voting.rank_lt_of_lt
- rank_score_veto_core_distortion_lower_boundFor any natural number m with 2 ≤ m and any positional scoring vector s : Fin m → ℚ, there exist positive natural numbers n1 and n2 such…
- connected_independence_local_clique_card_boundLet r and s be integers at least three and let d be an integer with 3r+3s<d+10. A connected finite simple graph with independence number…
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_a001One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- CommunicationComplexity.PublicCoin.FiniteMessage.Protocol.exists_good_randomnessExistence of good randomness for derandomization. Let $\Omega$ be a finite probability space and let $X$ and $Y$ be finite input sets. Let…
- mondrian_prime_area_shape_boundFor distinct primes p and q, if t+r=2e, at most r plus floor(log_p(q)) plus one shapes of area q times p^t fit in the q times p^e square.
- discrete_level_one_to_three_sharp_constant_of_lt_threeThe sharp level 1 to 3 inequality holds for all n < 3 (i.e. n = 1, 2) because W_3[f,g] = 0 and the left-hand side is nonpositive by…
- SocialChoice.FairDivision.Divisible.cutAndChoose_isEnvyFreeBoth agents are envy-free at any fair cut point. This combines
chooser_isEnvyFree(unconditional) andcutter_isEnvyFree_of_fair… - ordered_ramsey_monotone_cycle_alternating_path_twoFor all integers k ≥ 3, the ordered Ramsey number of the monotone cycle MC_k and the alternating path AP_2 is equal to k.
- cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core_a0000000One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core: under the layer-free tight-cover…
- nat_scaled_floor_gap_thresholdLet n,N,k,K be natural numbers with n positive, k*N at most K*n, and (K+1)*n at most (k+1)*N. For natural i at most j, j-i is at most k if…
- KnapsackAuction.welfareMaximizer_geKnapsackAuction.welfareMaximizer_ge
- cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core_b100One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core: under the layer-free tight-cover…
- two_ray_integer_atom_coeff_sum_le_primitiveFor an additive subgroup of integer-valued functions, let x have no proper nonzero nonnegative subgroup subvector. Given nonnegative…
- condorcet_product_uniform_half_score_obstructionThere is a strict regular tournament on 23 candidates, every candidate beating exactly 11 others, and a root map for ordered triples. Each…
- brgc_inverse_concatThe inverse Gray rank of a concatenation has the prefix inverse rank followed by the suffix inverse rank, complemented exactly when the…
- five_point_zero_sum_atom_classificationFor the five planar box points (1,1),(1,0),(0,1),(-2,0),(0,-2), every nonzero nonnegative integer atom in their zero-sum kernel has…
- condorcet_mutual_bad_outsiders_partitionIf two challenger claims are incompatible because each challenger lies in the other committee, and each has at least half the voter…
- cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core_b101One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core: under the layer-free tight-cover…
- mondrian_ordered_shape_halfTwice the number of available unordered dimension pairs is at most one plus the number of ordered dimension pairs fitting in the square.
- Fin.succSuccAbove_predPredAboveFin.succSuccAbove_predPredAbove
- condorcet_qr23_selector_completeEvery three-element subset of Fin 23 is the member set of some indexed triple.
- equal_length_proportional_cake_prefix_volumeIn any equal-length proportional cake allocation C : Fin n → Set ℝ for n ≥ 1 under the identical valuation profile where each agent values…
- postage_stamp_number_neg_two_add_one_eq_iffFor odd h ≥ 5, the negative-allowed three-stamp number misses n_h(2) = ⌊(h²+6h+1)/4⌋ by exactly one, n♭_h(2) = n_h(2) - 1, if and only if…
- op75_block_encoding_templateThe seven-layer block encoding is a fixed prefix, the positive coefficient encoding, a fixed middle, the negative coefficient encoding,…
- sweep_query_cardFor all natural numbers M, N, r, and j with r + 1 < M and j < N, the cardinality of the sweep query satisfies (sweep_query M N r j).card =…
- op869_graph_from_predecessorsThe simple graph on the ordered vertices Fin n whose edge from an earlier vertex a to a later vertex b exists exactly when a is in the…
- rpow_antitone_of_nonneg_antitoneRaising nonneg antitone sequences to a positive power preserves antitonicity.
- VNM.NotContinuous.not_continuousVNM.NotContinuous.not_continuous
- integer_interval_subset_of_nonempty_inter_of_no_endpointsIf an integer interval [a, b] intersects [l, r] and contains neither endpoint l nor r, then [a, b] is contained in [l, r].
- discrete_poincare_monotone_booleanLet $U$ be a finite non-empty type with decidable equality, and let $f : (U \to \mathrm{Bool}) \to \mathrm{Bool}$ be a monotone function.…
- tarski_query_complexity_dim_le_succDimension reduction: any query algorithm finding a fixed point in dimension k + 1 in at most q queries can be simulated in dimension k…
- cycle_power_fifteen_tight_type_sequence_two_iff_three_core_a1000001One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_two_iff_three_core: under the layer-free tight-cover…
- LinearMap.continuous_iInfFor bilinear maps in suitably well-behaved spaces with
IsModuleTopology, taking the infimum in one argument is stillContinuous, by… - mondrian_two_prime_factor_pair_encodingA positive factor pair of q^s times p^t has complementary q exponents summing to s and p exponents summing to t.
- op_193_hom_cycle_stepFor all integers k ≥ 2 and r ≥ 2 * k - 2, there exists a graph homomorphism from the G-stable Kneser graph KG(C_{r+2} ⊔ K_1, k) to the…
- GameTree.valueList_eq_map
valueList lis exactlyl.map value. Useful for rewriting. - simple_graph_cycle_power_seven_cover_four_tight_one_iff_sixIn a tight cover of C_n^7 (n ≥ 22) by 4 equivalence subgraphs (every distance-7, 6, 4 pair covered exactly once, every class spanned by a…
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_b001One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- SocialChoice.Voting.rank_lt_iffSocialChoice.Voting.rank_lt_iff
- Fin.succSuccAbove_self_applyFin.succSuccAbove_self_apply
- contiguous_interval_family_depth_lower_boundFor all integers R ≥ 1 and d ≥ 0 there is a finite rooted tree, properly colored with the 4 colors 0..3, with at most 11(2R+1)^d vertices,…
- cycle_power_fifteen_tight_type_sequence_shape_rules_core_v81_90Window refutation for k = 15: in the layer-free tight-class model on the integer line (x p j: the class starting at p contains p + j;…
- probabilistic_serial_fractional_assignment_two_split_swapTwo agents whose first choices are item 1 (agent 0) and item 0 (agent 1) each get their first choice entirely under probabilistic serial.
- ranking_kendall_tau_selfA ranking is at Kendall tau distance 0 from itself.
- Fin.predPredAboveThe preimage of
mundersuccSuccAbove i j hijgiven thatmis not equal toiorj. - sumset_rep_count_eq_zero_of_ltFor any k ≥ 1, h, q, and integer s < h + 1, the representation count ν_q(s) is zero.
- block_insertion_residual_cost_bound_of_gtGiven a type α with decidable equality, a cost function c : α → NNReal, a natural number k : ℕ with 1 ≤ k, a bundle B : Finset α with k ≤…
- wild_normalized_array_disjoint_witness_pair_countLet n>=3 and let A be a symmetric idempotent row-injective array on Fin n. Index its ordered witnesses by W={(x,y):x!=y}, with support…
- cycle_power_fifteen_tight_type_sequence_one_alternates_core_alt1110110One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_alternates_core: under the layer-free tight-cover…
- cycle_power_fifteen_tight_type_sequence_one_alternates_core_alt00000100_p4Sub-branch of the window refutation cycle_power_fifteen_tight_type_sequence_one_alternates_core_alt00000100 (one subtree of its case…
- exists_strictly_ordered_intervalsFor every countable linearly ordered type A, there exists a family of strictly separated intervals [l(a), r(a)] in (0, 1/2] such that a <…
- int_box_twoThe two-dimensional integer box ⟦−m, m⟧² = {(x, y) ∈ ℤ² : |x|, |y| ≤ m}.
- sumset_dot_product_setFor natural numbers h, k, and q, sumset_dot_product_set h k q is the finset of all values dotProduct x (sumset_finset_sorted_vector k A)…
- GameTree.valueList_nilGameTree.valueList_nil
- alpha_elementary_cell_step_binary_xorAn elementary operation changes exactly the boundary bit immediately before the untouched suffix.
- cycle_power_fifteen_tight_type_sequence_four_iff_five_core_a0000One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_four_iff_five_core: under the layer-free tight-cover…
- standard_example_reduction_min_max_subposetLet P be a finite poset of height 2 and let (u, v) be a min-max incomparable pair in P. If d ≥ 3 and P is S_d-free, then the subposet…
- op_258_exists_divergent_block_indicesFor any positive antitone sequence a : ℕ+ → ℝ with divergent sum and any n₀, there exist l ≥ 3 with 2^l ≥ n₀ and strictly increasing r :…
- latin_partition_is_wideEvery Latin Young diagram is wide: if a Young diagram $\mu$ admits a Latin tableau of shape $\mu$ and type $\mu'$ (…
- simple_graph_multi_radio_number_path_three_one_of_leFor every n >= 8 the (1,3)-radio number of the path P_n is exactly 7: the case m = 1 of the thread's goal (8m - 1 for n >= 4m + 4).
- west_stack_sortWest's stack-sorting map s acts on a list by maintaining an auxiliary stack, popping elements strictly smaller than the next input element…
- cauchy_binet_detFor any commutative ring R, natural numbers m and n, and matrices A : Matrix (Fin m) (Fin n) R and B : Matrix (Fin n) (Fin m) R, the…
- postage_stamp_basis_range_ge_of_mod_four_eq_twoFor h = 4w − 2 (w ≥ 1), the set A = {−w, w, w + 1} satisfies n_h(A) ≥ (w + 1)h = (h² + 6h)/4.
- energy_filter_centered_binomial_fourth_row_reindexFor any natural k, the finite sum of the fourth powers of centered binomial weights equals the sum of the fourth powers of row 2k divided…
- Matrix.schurTriangulationBasisThe change of basis that induces the upper triangular form
A.schurTriangulationof a matrixAover an algebraically closed field. - geodetic_c_condition_iff_product_condition_twoLet d ≥ 1 and let c : Fin d → ℕ be a monotone nondecreasing sequence with c(0) = 1. Then c satisfies the geodesic product condition for K…
- Matrix.diag_mul_of_blockTriangular_idFor upper-triangular matrices, the diagonal of a product is the product of the diagonals. This is a specific case of a more general…
- cycle_power_fifteen_tight_type_sequence_two_iff_three_core_a000101One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_two_iff_three_core: under the layer-free tight-cover…
- GameTree.optStrategy_isSubgamePerfectOptimality of
optStrategy: for every subtreeg, every playeri, and everyi-variant deviationσ', the deviating outcome is… - ejr_good_of_low_support_candidateIf candidate c is approved by fewer than n/m voters (m times its supporter count is below n), then for any k-committee P with c not in P,…
- cycle_power_fifteen_tight_type_sequence_one_alternates_core_alt1100One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_alternates_core: under the layer-free tight-cover…
- KnapsackAuction.welfareMaximizingAllocationRule_isMonotoneKnapsackAuction.welfareMaximizingAllocationRule_isMonotone
- tile_walsh_mul_eq_zeroLet E and T be subsets of Fin d → ZMod 2 such that E + T is the universal set and |E| * |T| = 2^d. For every nonzero vector u : Fin d →…
- exact_steiner_hopset_layered_dag_steiner_shortcutLet V and W be finite types, Gv a directed graph on V and ℓ : V → ℕ a layering such that every arc u → v of Gv has ℓ v = ℓ u + 1 (a…
- cycle_power_dyadic_neighbour_weight_boundA tight rooted dyadic class satisfies a uniform weighted bound for the ordinary distances one below the dyadic long distances, with a…
- GameTree.HasOnlyRootSubgamesA fixed
GameTreehas no proper subgames when every subtree is the root itself. This is the pure finite-tree analogue of having no… - cauchyBinetCauchy–Binet formula for rectangular matrices: if
Aism × nandBisn × m, thendet(A * B) = ∑_S det(A[:,S]) * det(B[S,:])… - binary_deletion_collision_eq_q_ary_twoFor every k, n and binary word w of length n, the binary k-deletion collision sum of w equals the q-ary k-deletion collision sum (q = 2)…
- electrical_flow_cross_termIf F is a skew-symmetric flow on Fin k satisfying the voltage law d i j * F i j = h i - h j for all i ≠ j, and G is a skew-symmetric flow…
- three_token_k2n_domination_arithFor every integer n ≥ 4, (n / 2).choose 2 + (n - n / 2).choose 2 + n - 2 ≤ (n + 1)^2 / 4 - 2.
- energy_filter_centered_row_sumFor any real integer function, summing it over offsets from −k to k equals summing it at j−k over j from 0 through 2k.
- bivalued_two_agent_efx_family_feasible_of_envy_free_sidesFor real r > 1, positive scales a0, a1 and natural numbers n1, n2, n3, n4: if (hA) unless n1 = n3 = n4 = 0 with n2 odd there is a…
- ido_remaining_chores_cost_le_one_thirdIn an identically ordered instance with nonnegative costs and maximin share 1 for each agent, every remaining chore g in V (with index at…
- mondrian_prime_pow_gapFor p at least two, c less than p, and r at least two, c * (r + 1) is less than p to the r.
- sumset_sum_vectors_finset_memFor any natural numbers h and k and any vector x : Fin k → ℤ, x belongs to sumset_sum_vectors_finset h k if and only if x belongs to…
- hn_quotient_matrix_charpolyFor every natural number n, the characteristic polynomial of the quotient matrix hn_quotient_matrix n equals (Polynomial.X + Polynomial.C…
- GameTree.valueList_consGameTree.valueList_cons
- grid_arrangement_column_deviation_subset_sum_leFor any grid arrangement $S$ of order $n \ge 3$ and any column subset $J$ of cardinality $p$, the column-deviation sum…
- efx_pareto_lock_padded_sanityFor every k the padded starting allocation is partial EFX and has the claimed baseline utilities.
- tarski_box_query_le_imp_query_complexityThe box-local invariant implies the ambient query complexity notion, by taking the full box [0, n−1]^k (needs n ≥ 1 since Fin n has no…
- hunger_firing_stateGiven a positive natural number n, a linearly ordered type α, and a vector h : Fin n → α, hunger_firing_state h is the smallest index i :…
- cycle_power_fifteen_tight_type_sequence_six_iff_seven_core_a1110One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_six_iff_seven_core: under the layer-free tight-cover…
- monotoneMixtureWeight_nonnegIf $P : \mathbb{N}^+ \to \mathbb{R}$ is antitone (nonincreasing), then the mixture weight $w_k = k(P(k) - P(k+1))$ is nonnegative for…
- integer_positive_line_boundary_decompositionFor a strictly positive finite integer vector x and a mixed-sign integer direction w, explicit integer vectors u=w(i)x-x(i)w and…
- List.argMaxOn_memThe chosen maximizer is a member of the list.
- forest_greedy_enveloped_tie_bias_boundFor an enveloped fixed-parity law and a fair coin, the probability of a greedy increase from a positive discrepancy j is bounded by the…
- cycle_power_fifteen_tight_type_sequence_one_alternates_core_alt00000100One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_alternates_core: under the layer-free tight-cover…
- probabilistic_serial_fractional_assignment_two_sameSanity check: when both of two agents rank item 0 first, probabilistic serial gives each agent half of each item.
- cycle_power_fifteen_tight_type_sequence_ten_iff_eleven_core_a0One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_ten_iff_eleven_core: under the layer-free tight-cover…
- cycle_power_fifteen_tight_type_sequence_twelve_iff_thirteen_core_b00000One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_twelve_iff_thirteen_core: under the layer-free…
- one_layered_recurrenceFor integers r ≥ 2 and m ≥ r, the maximum number of layers F(m, r) satisfies F(m, r) ≤ F(⌊(m - 1) / 2⌋, r) + F(⌈(m - 1) / 2⌉, r) + F(m -…
- GameTree.IsNashAtRoot-scoped Nash equilibrium predicate for a fixed
GameTreeroot. This is definitionally the existingIsNashEquilibrium, with the… - young_lattice_rank_is_ranked_posetFor any m and n, the rank function young_lattice_rank makes L(m, n) into a ranked poset in the sense of is_ranked_poset.
- condorcet_product_clone_uniform_half_obstructionFor a root map on ordered triples of m candidates, suppose each root has exactly m squared preimages under uniform iid sampling and the…
- IsCompact.closure_continuous_sSupA version of
IsCompact.continuous_sSupwith a slightly weaker hypothesis on the setK, that its closure is compact (but the set itself… - op223_first_replacement_spectral_lowerReplacing edge 0-1 with 4-2 in the example tree yields a graph whose spectral radius is greater than 209/100.
- 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…
- GameTree.IsNashAt.toSubgamePerfectOn_of_hasOnlyRootSubgamesIf a tree has no proper subgames, root Nash equilibrium already implies subgame perfection on that tree. This is the pure finite-tree form…
- mondrian_prime_free_area_shape_boundFor distinct primes p and q, if t+r=2e, at most r plus floor(log_p(q)) plus one shapes of pure p-power area p^t fit in the q times p^e…
- condorcet_equal_coalition_root_sinkIn a positive finite electorate, let a family of challenger claims all have exactly the same voter coalition as one claim with at least…
- GameTree.outcome_le_value₀_of_iVariant_zeroPlayer 1's security. If player 1 plays
optStrategy(soσ'is a0-variant, leaving player 1's choices fixed), then player 0's… - op_517_zero_excess_iff_exists_walkTwo rank-3 signotopes on Fin m have braid-move excess 0 if and only if there exists a walk in the higher Bruhat order B(m, 2) between them…
- op_517_zero_excess_of_le_twoFor any instance inst of WiringDiagramPair on m pseudolines with m ≤ 2, there are no ordered triples in Fin m, so inst.u = inst.v holds…
- ten_vertex_exchange_family_eqThe 52 explicit triangle edge sets are exactly the triangle family of the ten-vertex graph.
- GameTree.outcome_NodeGameTree.outcome_Node
- 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…
- thermomajorization_full_budget_zero_errorFor any natural number n with 1 ≤ n, measuring all n - 1 binary probes gives zero minimax missed error: thermomajorization_minimax_error n…
- eval_ordered_tripleGiven a function chi : OrderedTriple α → ℤˣ assigning units of ℤ to ordered triples in a linearly ordered type α, and elements x, a, b : α…
- plurality_votesGiven a preference profile prof assigning a linear order over candidates C to each voter in V, the plurality count of candidate c 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]) ≤…
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_a0000111One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core_b11111One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core: under the layer-free tight-cover…
- dedekind_number_posEvery Dedekind number is strictly positive.
- mondrian_prime_free_height_encodingIf x*y=q^s*p^t for primes p and q and q does not divide x, then y is q^s times a power of p; the primes need not be distinct.
- postage_stamp_basis_range_add_two_boundsIf [0, m² + 4m + 1] is contained in the (2m+1)-fold sumset of {a, a+x, a+y} with 0 < x < y and a < 0 (where m ≥ 2), then x and y are…
- condorcet_subset_potential_of_ordering_boundFor any finite family of challenger claims with nonnegative integer weights, if every strict candidate ranking has satisfied-claim weight…
- condorcet_quadratic_subset_potential_half_barrierLet an integer-valued subset potential be represented by arbitrary integer vertex coefficients and ordered-pair coefficients with zero…
- Fin.succSuccAbove_succAbove_comm_applyPointwise form of commuting deletion of one slot with deletion of a pair.
- transitions_le_two_mul_card_of_bool_labelsFor any positive natural number m with [NeZero m], any type ι, any finite set L of elements of ι, any natural number k, any coloring α :…
- positive_fibre_threeThe positive fibre of a function u : OrderedTriple α → ℤˣ on a linearly ordered type α is the function on OrderedTriple (WithTop α) with…
- postage_stamp_basis_rep_mod_twelve_eq_nineFor any r : ℕ and any m ≤ 36r² + 72r + 33, there exist non-negative integers s, t, u such that s + t + u = 12r + 9 and -s(2r+2) + t(2r+2)…
- mondrian_prime_free_height_two_chain_encodingIf x*y=q^s*r*p^a for primes p,q,r with p≠r, and q does not divide x, then y lies in one of the chains q^s*p^b or q^s*r*p^b.
- op_517_zero_excess_of_adjIf two wiring diagrams (represented as rank-3 signotopes u and v on Fin m) are adjacent in the higher Bruhat graph…
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_a0000101One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- op75_tm2_output_linear_boundFor any finite TM2, there is a constant C such that for every input and output, a halting run of at most n steps has output length at most…
- IsPositiveAffineOf.preserves_representationIf
urepresents a preference, so does any positive affine transform. [MSZ 2.22] - postage_stamp_number_neg_two_of_odd_cases_twoFor h = 2m+1 with m ≡ 5 (mod 6), m ≥ 5: no coprime x < y and a < 0 satisfy the Theorem 4.1 inequalities at range m² + 4m = n_h(2) - 2.
- op869_many_shared_colorsIf |B| < |A| and every element of A meets at least d elements of B, then at least d elements of B lie in at least two of the sets.
- exists_multi_radio_labeling_pathFor all n, m, k there is an (m,k)-radio labeling of the path P_n: on vertex v put the m labels (k+1)*(m*v + a) for a < m.
- VNM.ContinuityContinuity (Archimedean / MSZ Axiom 2.12): for
L₁ ≿ L₂ ≿ L₃, there existsθ ∈ [0,1]such thatL₂ ∼ [θ L₁, (1-θ) L₃]. - energy_filter_centered_binomial_fourth_mass_asymptoticAs k tends to infinity, the fourth power sum of row 2k of Pascal’s triangle, divided by the fourth power of its central coefficient and by…
- condorcet_ordering_certificate_excludes_common_obstructionFor any finite family of challenger claims with nonnegative integer weights, if in every strict ranking their total satisfied weight is…
- tournament_near_regular_card_degreesIn any near-regular tournament on 2m vertices with m ≥ 1, exactly m vertices have out-degree m - 1 and exactly m vertices have out-degree m.
- thermomajorization_missed_errorFor dimension n and probe set F : Finset ℕ, thermomajorization_missed_error n F is the supremum over all nonincreasing probability vectors…
- energy_filter_centered_binomial_fourth_step_integralFor k≥1, the integral of the fourth power of the centered binomial weight at floor(√k x) equals the finite sum of the fourth powers over…
- PureU1.VectorLikeEvenPlane.n_cond₂PureU1.VectorLikeEvenPlane.n_cond₂
- postage_stamp_number_neg_two_add_four_le_of_mod_sixty_eqFor odd h ≥ 5 with h ≡ 59 (mod 60), n♭_h(2) ≤ n_h(2) - 4, where n_h(2) = ⌊(h²+6h+1)/4⌋.
- geodetic_c_condition_iff_product_condition_threeLet d ≥ 1 and let c : Fin d → ℕ be a monotone nondecreasing sequence with c(0) = 1. Then c satisfies the geodesic product condition for K…
- SocialChoice.FairDivision.Divisible.MeasureInstance.IsProportionalProportionality for a measure-based divisible instance, stated in
ENNReal. - is_cohen_macaulay_two_complexA finite simplicial complex given by a set of facets in a linearly ordered vertex type V is defined to be Cohen-Macaulay over a field k…
- mixture_representation_monotone_distributionLet $P : \mathbb{N}^+ \to \mathbb{R}$ be a nonincreasing probability distribution on the positive integers, so that $P(k) \ge 0$ for all…
- ejr_chain_of_deletable_voterIf a voter's ballot is empty or misses at most one candidate, deleting that voter preserves the existence of an EJR chain: the same…
- tarski_box_query_le_zero_dimDimension zero is free: in dimension 0 (the one-point box) one query suffices, for every n and every box.
- List.argMaxOn_geSoundness: every element's
f-image is≤the chosen maximizer's. - IsPositiveAffineOf
vis a positive affine transformation ofu:v(x) = a · u(x) + bwitha > 0. Two utility functions related by a positive affine… - condorcet_voter_bad_outsiders_eq_min_rankFor a permutation
permofFin mand a nonempty subset S, the number of candidates outside S ranked strictly above every element of S… - cubic_power_component_cube_non_bentLet E be a finite field of characteristic 2 with 2^(2m) elements. If β in E is a nonzero cube, then the Boolean function x ↦ Tr(β x^3) is…
- card_filter_gt_card_filter_of_ltFor f : α → β with β linearly ordered and α finite, if f a < f b then strictly fewer elements of α have f-value above f b than above f a.
- postage_stamp_number_neg_two_of_odd_range_geIf A is bounded above and h-fold covers [0, R], its h-range is at least R.
- Fin.succSuccAbove_ne_fstFin.succSuccAbove_ne_fst
- cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core_a01011One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core: under the layer-free tight-cover…
- geodesic_transversal_number_le_edge_geodesic_transversal_numberFor any connected simple graph G that admits a finite edge geodesic transversal, the vertex geodesic transversal number of G is bounded…
- IsPositiveAffineOf.preserves_leA positive affine transform preserves the order:
u x ≤ u y ↔ v x ≤ v y. - cycle_power_fifteen_tight_type_sequence_two_iff_three_core_a111One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_two_iff_three_core: under the layer-free tight-cover…
- cycle_power_fifteen_tight_type_sequence_shape_rules_core_v30_41Window refutation for k = 15: in the layer-free tight-class model on the integer line (x p j: the class starting at p contains p + j;…
- cycle_power_fifteen_tight_type_sequence_four_iff_five_core_b00One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_four_iff_five_core: under the layer-free tight-cover…
- simple_graph_size_ramsey_star_star_forestLemma 2.3 of arXiv:2610.25958: for positive integers p, q, n_1 ≥ ... ≥ n_q, r̂(K_{1,p}, ⊔_{i=1}^q K_{1,n_i}) = ∑_{i=1}^q (p + n_i - 1).
- cycle_power_fifteen_tight_type_sequence_six_iff_seven_core_a111111One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_six_iff_seven_core: under the layer-free tight-cover…
- rank_score_veto_core_opposition_cost_leFor every voter v who ranks c* strictly above a, the candidate distance d(a,c*) is at most twice the voter's own distance to c*; summing…
- rank_potential_offline_fetch_boundAt an offline fetch, the increase in rank potential is at most k (Lemma 3.3(i)).
- exists_connected_all_powers_well_covered_diam_geFor every positive integer D, there exists a finite connected simple graph G with diameter at least D such that every positive power G^d…
- alpha_lexical_first_negative_step_existsA lexical sequence with at least two cells has an elementary lexical successor at its first negative cell.
- binary_deletion_num_embeddingsFor natural numbers k and n, a binary word u of length n - k, and a binary word w of length n, binary_deletion_num_embeddings k n u w is…
- is_ultrametric_transition_of_eq_constFor a natural number n, a linearly ordered type α, a matrix P : Matrix (Fin n) (Fin n) α, and an element c : α, if all off-diagonal…
- WickContraction.sndFieldOfContractThe largest of the two positions in a contracted pair given a Wick contraction.
- Dimension.Exponent.coe_lt_coeDimension.Exponent.coe_lt_coe
- comparison_triangle_kappa_mem_eval_kerEach triangle relation vector kappa_abc evaluates to zero on every strict order: d_ab d_ac - d_ab d_bc + d_ac d_bc - 1 = 0.
- lower_ones_matrix_apply_selfThe diagonal entries of L are 1.
- op223_matrix_spectral_lowerA negative quadratic form for tI minus a Hermitian real matrix certifies that its real spectral radius exceeds t.
- postage_stamp_number_neg_two_of_odd_family_1For m ≥ 2 with m ≢ 2 (mod 3), the set {-1, 2, m} (2m+1)-fold covers [0, m² + 4m] = [0, n_h(2) - 2].
- GameTree.value_Node_geKey optimality lemma: at a
Node m h t, the moverm's coordinate of the backward-induction value dominates every child's. - sparse_graph_state_fisher_core_kFor integers d >= 2 and c >= 0, k(d, c) is the least positive integer k such that floor(k^2 / 4) >= d*k + c.
- mixed_diamond_fan_ramsey_bound_all_singletons_one_fan_colourCase b = 1 with every singleton of the unique fan colour: if d ≥ j*a + j and the statement holds at (a, 0) in dimension d-j, then χ has a…
- descending_band_setFor an integer d and positive integers r ≤ L, the descending band set A_{r,L} is the union over j from 0 to r-1 of the integer intervals…
- LinearMap.BilinForm.continuous_iInfAlias of
LinearMap.continuous_iInf'that takesLinearMap.BilinForm. - cycle_power_fifteen_tight_type_sequence_one_alternates_core_alt1111One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_alternates_core: under the layer-free tight-cover…
- op223_nonsustainable_tree_fin_fourEvery non-sustainable tree on four vertices is isomorphic to the star graph K_{1,3}.
- probabilistic_serial_fractional_assignment_two_splitTwo agents whose first choices are item 0 (agent 0) and item 1 (agent 1) each get their first choice entirely under probabilistic serial.
- VNM.NotComplete.independentVNM.NotComplete.independent
- mondrian_seven_rects_defect_geWithin the seven-rectangle family, the defect is always at least 280 (in particular never 0): if p, q are odd then p² − 19q² ≡ 2 (mod 4),…
- KnapsackAuction.fractionalGreedyWelfare_ge_zeroOneWelfare_of_optimalIf the ratio-sorted greedy fractional allocation is optimal for the fractional relaxation, then its welfare dominates the welfare of the…
- ContinuousLinearMap.continuous_iInfContinuousLinearMap.continuous_iInf
- cycle_power_fifteen_tight_type_sequence_ten_iff_eleven_core_b10One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_ten_iff_eleven_core: under the layer-free tight-cover…
- Submodule.inf_ne_bot_of_rank_ltSubmodule.inf_ne_bot_of_rank_lt
- cycle_power_fifteen_tight_type_sequence_shape_rules_core_v111_120Window refutation for k = 15: in the layer-free tight-class model on the integer line (x p j: the class starting at p contains p + j;…
- is_identically_orderedAn instance of m chores and n agents with cost functions c is identically ordered (IDO) if for every agent i, the cost function c_i is…
- stein_param_inj_onThe map sending (d, u, v) to d^2 * (u^4 + 4 * v^4) is injective on stein_param_set.
- GameTree.IsSubgamePerfectA strategy is subgame-perfect (SPE) if, at every subtree, no player can strictly improve their payoff by a unilateral deviation —…
- isASPath_idThe identity function a(t) = t is an ascending shallow path coordinate function.
- perm_order_eq_prod_and_sum_prime_power_parts_leLet k ≥ 1. If q is the order of some permutation of k elements and S(q) is the set of maximal prime-power divisors of q, then q =…
- digraph_nested_parents_overlap_generalFor k transitive low vertices pointing to q, nested common-predecessor counts k+3−t force common-predecessor overlap at least twice…
- pathCertRunBoundThe accumulated signed greedy count is bounded by the finite-state potential.
- shifted_geometric_distribution_hasSumFor any parameter 0 ≤ a < 1 and shift L ∈ ℤ, the shifted geometric distribution G_L has sum 1 over ℤ.
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_a0101One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- postage_stamp_basis_range_add_one_le_of_neg_of_oddFor odd h ≥ 1, every 3-element set A of integers containing a negative integer has h-range n_h(A) < ⌊(h² + 6h + 1)/4⌋ = n_h(2); hence…
- mondrian_partition_width_dvd_of_height_prime_chainSuppose d divides the square side and all tiles whose widths are indivisible by d have heights C times powers of a fixed prime p, with…
- comparison_triangle_gramThe Gram matrix of the triangle relation vectors is U_triangle^T U_triangle = 3 I + 1 1^T: each kappa_abc has squared norm 4 and two…
- mondrian_prime_square_cofactor_side_boundA side q^2 times p^a fitting in a q times p^e square satisfies a plus floor(log_p(q)) plus one at most e, for distinct primes.
- GameTree.outcome_optStrategy_eq_valueKey lemma: the outcome of the backward-induction strategy equals the backward-induction value vector at every game tree. This is the…
- op_193_cubic_tight_if_cycle_lowerFor k at least 3 and m at least k((k-1)²+1), the stable k-set graph of the m-cycle plus an isolated vertex has chromatic number m-2k+3,…
- davenport_constant_support_four_int_box_three_ge_oddTheorem 3 of arXiv:2610.16562, odd m: for every odd m ≥ 2, the maximal length of a minimal zero-sum sequence over [[-m,m]]^3 with support…
- condorcet_polynomial_potential_dual_boundLet a finite signed subset polynomial be a sum of monomials indexed by a specified finite support. Suppose weighted rooted removal sets…
- List.argMaxOnA chosen maximizer of
fon the non-empty listhead :: tail, computed by a left fold that keeps the running maximizer (ties keep… - cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_a00001100001100000One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- op_258_exists_divergent_capacity_coveringIf a positive antitone profile a has infinite sum in ENNReal, then for any threshold n₀, there exists l ≥ 1 with 2^l ≥ n₀, pairwise…
- digraph_general_robust_two_cycle_free_cutAssuming the displayed robust two-cycle criterion, every two-cycle-free part of size at least d in a graph with outdegree at least d on…
- is_aau_ruleAn allocation rule satisfies alternating advantage under unanimity (AAU) if at every unanimous preference profile, for any two agents i…
- prioritized_borel_finite_lex_limit_stabilizesA lexicographically nondecreasing sequence of binary profiles with a coordinatewise limit having finite support is eventually equal to…
- LinearMap.continuous_iSup'A specialization of
LinearMap.continuous_iSupto finite dimensional spaces, in place of requiring a (non-instance)IsModuleTopology. - ejr_adjacent_committees_existsFor every approval profile with at least one voter and every k smaller than the candidate count, there exist nested committees W subset V…
- satisfies_geodetic_product_conditionA sequence c : Fin d → ℕ satisfies the geodesic product condition for bound K if for every index i : Fin d, the product of c(j) over all j…
- permutation_partial_assignment_card_bound_of_switchingIf a finite set of permutations is closed under undoing any one forced assignment by an image swap, its number extending an injective…
- bipartite_subgraph_poset_dimension_pow_lower_boundLet V be a finite type with decidable equality, G a simple graph on V with decidable adjacency, and A, B subsets of V covering V such that…
- Kruskal.processEdges_optimalOptimality of the greedy edge-selection sweep. Let $\mathit{edges}$ be a list of weighted edges on $n$ vertices, sorted in nondecreasing…
- ErrorCorrectingCodes.Codeword.hamming_ball_sizeCardinality of Hamming balls. Let $\alpha$ be a finite alphabet, and regard a codeword of length $n$ as a function…
- pyranim_seqpyranim_seq n is the finite set of all functions l : Fin n → Fin (n+2) that are weakly increasing and satisfy 1 ≤ l i ≤ i+2 for every i.…
- OneLayeredFamilyGiven a type V and a natural number r, a 1-layered family of r-subsets on V is a structure OneLayeredFamily (V : Type*) (r : ℕ) consisting…
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_b0000101One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- wheel5_scaled_list_uncolorableFor all integers t ≥ 0 and b ≥ 3t + 2, there exists a list assignment L* on the 5-wheel W₅ such that |L*(x)| = b * f_W(x) + t for every…
- comparison_triangle_kappaThe real triangle relation vector kappa_abc : comparison_feature2 n → ℝ of a triangle a < b < c: kappa_abc = e_(ab,ac) - e_(ab,bc) +…
- op223_no_nonsustainable_tree_fin_threeThere are no non-sustainable trees on three vertices.
- davenport_box_three_even_sequence_minimalFor m ≥ 2 even, T(m) is a minimal zero-sum sequence: no proper nonempty subsequence sums to zero.
- cycle_power_fifteen_tight_type_sequence_ten_iff_eleven_core_b110One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_ten_iff_eleven_core: under the layer-free tight-cover…
- arrangement3_e4_zero_iff_is_magicAn arrangement of order 3 satisfies the four-term line-sum energy zero condition $E_4(S) = 0$ if and only if it is a magic square.
- chirotope_three_graphThe mutation walk graph of uniform rank-3 chirotopes on Ω is the simple graph whose vertices are uniform rank-3 chirotopes chi :…
- thrifty_greedy_stepFor a non-empty set of remaining timely items
Rwith witnesshR : R.Nonempty,thrifty_greedy_step R hRreturns theTimelyBinwhose… - candidate_rankGiven a finite candidate type C with decidable equality, a linear order ord on C, and a candidate c in C, candidate_rank ord c is the…
- poset_heightThe height of a finite partial order α: one less than the maximum cardinality of a chain in α, i.e. the largest n such that α admits a…
- GameTree.IsSubgamePerfectOn.toNashAtRoot-scoped subgame perfection implies Nash equilibrium at the same root.
- op_153_intersective_quadratic_normalize_positiveIf the eventual subexponential difference bound holds for every degree-2 intersective integer polynomial that is strictly positive on all…
- simple_graph_cycle_power_three_layer_weight_eq_impIn the situation of the weight inequality, if Σ_i (2·[c i = c(i+3)] + [c i = c(i+2)]) = n then every class contains a pair at distance 3…
- tarski_box_query_le_mono_budgetThe box-local query invariant is monotone in the query budget: a box algorithm using at most q queries also satisfies the invariant for…
- ErrorCorrectingCodes.Codeword.hamming_boundHamming (sphere-packing) bound. Let $\alpha$ be a finite alphabet with $q = \abs{\alpha} > 1$ symbols, and let $C \subseteq \alpha^n$ be a…
- GameTree.value₀_le_outcome_of_iVariant_onePlayer 0's security. If player 0 plays
optStrategy(so the deviating profileσ'is a1-variant, leaving player 0's choices… - cycle_power_fifteen_tight_type_sequence_twelve_iff_thirteen_core_a1One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_twelve_iff_thirteen_core: under the layer-free…
- op_258_forces_all_of_forces_stepAssume that for every positive antitone profile a with Σ a i > 1 and every k ≥ 3, forcing a monochromatic K_k implies forcing a…
- partition_number_zeroThe integer-valued partition function partition_number evaluated at 0 equals 1.
- GameTree.valueGameTree.value
- simple_graph_is_tree_card_sub_two_le_sum_choose_degree_le_chooseFor a tree T on k ≥ 2 vertices, σ₂(T) = ∑_v C(d_T(v),2) satisfies k − 2 ≤ σ₂(T) ≤ C(k−1,2).
- digraph_weighted_center_strict54_certificateThe displayed 54-vertex graph is loopless, oriented, triangle-free and arc-dominated, has minimum outdegree seven and auxiliary…
- two_ray_integer_atom_coeff_sum_leLet x be an atom in the nonnegative part of an additive subgroup of integer-valued functions. If D*x=a*u+b*v for nonnegative subgroup…
- List.exists_argMax_onExistence of an argmax on a non-empty list under a total preorder. Since the preorder may lack antisymmetry, ties are allowed — we…
- KnapsackAuction.IsFeasibleFeasibility for a knapsack auction: * each agent's allocation lies in
[0,1]* the weighted allocation satisfies the total capacity bound - davenport_box_three_even_sequence_cardThe sequence T(m) (even case) has length 16m^3 - 16m^2 + 8m - 1.
- op562_not_consistent_eefx_of_ge_three_halvesFor any number of agents n at least 3 and any error factor rho at least 3/2, no consistent online algorithm can guarantee any positive…
- multiqubit_dof_inequality_failsFor every n ≥ 4, the multiqubit degree-of-freedom inequality fails strictly: 4 * n < 2^n + n.
- perm_distinct_abs_diffs_ascent_count_sub_half_unboundedFor any permutation (a_n) of the positive integers whose consecutive absolute differences are pairwise distinct, A(X) − X/2 is unbounded…
- cycle_power_fifteen_tight_type_sequence_four_iff_five_core_a110000One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_four_iff_five_core: under the layer-free tight-cover…
- integer_box_completion_subset_emod_ltIf every subset completed by an integer vector in the box [0,n-1]^r that vanishes modulo n also vanishes modulo n squared, each negative…
- cycle_power_fifteen_tight_type_sequence_twelve_iff_thirteen_core_b00001000000One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_twelve_iff_thirteen_core: under the layer-free…
- ExtensiveGame.ExtractsGameTree.spe_on_to_nash_atOn any extracted tree, root-scoped subgame perfection implies root Nash equilibrium through the ordinary
GameTreeequilibrium API. - KnapsackAuction.NonnegativeWeightsEvery public weight is nonnegative.
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_a011One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- not_leading_unit_monotonicity_conjectureThe statement
leading_unit_monotonicity_conjectureis false: The statement is FALSE. Counterexample: c = [1,0,3,0,3,1]. * c.length = 6 ≥… - simple_graph_equivalence_covering_number_cycle_power_dyadic_of_class_shapeUnder the numerical hypotheses of OP-205, the equivalence covering number is m+2 PROVIDED that every tight, exactly dyadically covered,…
- mondrian_prime_power_shape_boundFor k at least two and positive A with k times A equal to the area of a p-power square, the number of available shapes is at most the…
- Fin.succSuccAbove_eq_succAbove_succAboveFin.succSuccAbove_eq_succAbove_succAbove
- KnapsackAuction.welfareMaximizer_mem_feasibleBinaryAllocationsKnapsackAuction.welfareMaximizer_mem_feasibleBinaryAllocations
- cycle_power_fifteen_tight_type_sequence_shape_rules_core_v91_100Window refutation for k = 15: in the layer-free tight-class model on the integer line (x p j: the class starting at p contains p + j;…
- schur_two_upper_boundFor every integer k ≥ 3, every 2-coloring c : Fin (k^2 + k - 1) → Fin 2 admits a monochromatic solution to (x.val + 1) + (k - 1) * (y.val…
- unit_hamming_triangle_free_card_leFor every integer q ≥ 2 and every integer n ≥ 1, every finite set A : Finset (Fin n → Fin q) satisfying unit_hamming_triangle_free A…
- SocialChoice.FairDivision.Divisible.MeasureInstance.IsEquitableEquitability for a measure-based divisible instance, stated in
ENNReal. - cycle_power_dyadic_tight_class_spanningA nonempty subset attaining equality in the uniform dyadic weight bound contains both endpoints of its arc.
- op_153_witness_index_boundFor a degree-2 integer polynomial g strictly positive on the positive integers, every positive integer n with g(n) <= N satisfies n <= N,…
- nc_sum_growsAfter
fuelrounds ending with free men,∑ nextChoicegrew by ≥fuel. - prioritized_borel_exponential_profile_frontierFor every n, there is a set of 2^n pairs of length-n binary profiles in which distinct pairs are incomparable when both components are…
- Fin.succSuccAbove_leq_iff_leqFin.succSuccAbove_leq_iff_leq
- postage_stamp_number_neg_four_one_nine_two_add_six_leFor h = 419 (h ≡ 59 mod 60), the negative-allowed three-stamp number satisfies n♭_h(2) ≤ n_h(2) - 6, where n_h(2) = ⌊(h²+6h+1)/4⌋ = 44519.…
- cycle_power_fifteen_tight_type_sequence_one_alternates_core_alt00000100_p2Sub-branch of the window refutation cycle_power_fifteen_tight_type_sequence_one_alternates_core_alt00000100 (one subtree of its case…
- bruhat_order_three_graphThe higher Bruhat order B(α, 2) is the simple graph whose vertices are rank-3 signotopes u : OrderedTriple α → ℤˣ (subtypes of functions…
- symmetric_counterexample_bent_weight_diff_div_sixteenFor any even n ≥ 8 and any two bent functions g and h on (Fin n → ZMod 2), the difference between the Hamming weight of h and the Hamming…
- VNM.NotContinuous.independentVNM.NotContinuous.independent
- Fin.succSuccAbove_valFin.succSuccAbove_val
- cycle_power_fifteen_tight_type_sequence_one_alternates_core_alt00000100_p1Sub-branch of the window refutation cycle_power_fifteen_tight_type_sequence_one_alternates_core_alt00000100 (one subtree of its case…
- digraph_common_predecessor_vertex_incidence_boundFor an r-outregular finite digraph, the number of common-predecessor edge incidences repeated at a given vertex is at most the total…
- stein_param_maps_toThe map sending (d, u, v) to d^2 * (u^4 + 4 * v^4) maps each triple in stein_param_set to an integer satisfying is_stein_number.
- monotone_distribution_telescoping_sumFor any sequence $P : \mathbb{N}^+ \to \mathbb{R}$ and any positive integers $n \le N$, the sum $\sum_{k=n}^N \frac{w_k}{k}$ telescopes to…
- discrete_max_principle_stepIf w_ext(0) = 0 and 2*w_ext(l.succ) = w_ext(u l.succ) + w_ext(v l.succ) for all l, and V > 0 is the maximum of w_ext, then S = {j | w_ext…
- tarski_box_query_leBox-local Tarski query invariant: for every sub-box [a,b] (a ≤ b) of [n]^k there is a single deterministic query tree — depending only on…
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_b0000100One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- op_518_positive_fibre_adj_of_adjFor every natural number m > 0, and any functions u, v : OrderedTriple (Fin m) → ℤˣ that are rank-3 signotopes whose positive fibres are…
- seidel_matrix_codegree_eqFor any simple graph G on a finite vertex set V with Seidel matrix S and any pair of adjacent vertices u and v in G, four times the number…
- postage_stamp_basis_range_zero_one_ge_of_mod_four_eq_zeroFor h = 4w (w ≥ 1), the basis {0, 1, 2w + 1} = {0, 1, (h+2)/2} has h-range at least w(4w + 6) = (h² + 6h)/4: every integer in [0, w(4w+6)]…
- difference_squares_avoiding_gp3_boundsLet $p \ge 7$ be a prime and let $A \subset \mathbb{F}_p$ be nonempty. If the set of squared differences $(A - A)^2$ contains no…
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_a0000110001One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_a000001One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- simple_graph_adj_eigenvalues_sorted_antitoneThe sorted adjacency eigenvalues of a finite simple graph are nonincreasing in the index.
- davenport_constant_int_box_two_geFor every m ≥ 2, the Davenport constant of the box ⟦−m, m⟧² is at least 4m² − q(m), q(m) the smallest prime not dividing m: S(m) is a…
- LinearMap.continuous_iSupFor bilinear maps in suitably well-behaved spaces with
IsModuleTopology, taking the supremum in one argument is stillContinuous, by… - cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core_a01111001One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core: under the layer-free tight-cover…
- 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…
- carpool_delta_sumFor any integer threshold D : ℤ, integer discrepancies da db : ℤ satisfying da - db ≤ 29, and natural number k ≥ 1, the sum of delta_plus…
- simple_graph_is_tree_sum_choose_degree_eq_iff_pathFor a tree T on k ≥ 2 vertices, σ₂(T) = k − 2 if and only if T is isomorphic to the path P_k.
- qary_deletion_num_embeddingsFor natural numbers q, k, and n, a word u of length n - k over an alphabet of size q, and a word w of length n over the same alphabet,…
- prioritized_borel_lex_restrict_monotoneRestricting lexicographically ordered infinite binary profiles to any fixed finite prefix preserves their order.
- IsCompact.closure_continuous_sInfA version of
IsCompact.continuous_sInfwith a slightly weaker hypothesis on the setK, that its closure is compact (but the set itself… - Fin.succSuccAbove_comm_natAddFin.succSuccAbove_comm_natAdd
- matrix_eigenvalues₀_le_of_sub_posSemidefIf $A$ and $C$ are real symmetric matrices such that $C - A$ is positive semidefinite, then each ordered eigenvalue of $A$ is at most the…
- block_insertion_residual_cost_bound_of_leGiven a type α with decidable equality, a cost function c : α → NNReal, a natural number k : ℕ, a bundle B : Finset α with k ≤ B.card, and…
- collision_embedding_pair_countFor a binary word w of length m + 2, collision_embedding_pair_count m w is the number of ordered pairs (f, g) of strictly increasing maps…
- is_rank_three_uniform_chirotopeA function chi : OrderedTriple α → ℤˣ assigning units of ℤ to ordered triples in a linearly ordered type α is a uniform rank-3 chirotope…
- wild_triple_partition_large_order_mass_boundFor odd q>=100001, both canonical seal-event resource sums for q triples of vertices in K_(3q), with weight (21/20)^d/(3q)_d, are at most…
- tarski_slice_upper_boundMonotonicity preservation on coordinate slices (upper bound): fixing coordinate i to any value m ≤ b_i preserves the upper subinterval…
- GameTree.IVariantTwo strategies are
i-variants if they agree on all nodes NOT owned byi. I.e.,σ'is obtained fromσby changing only playeri's… - is_identically_ordered_zeroThe zero cost profile where all agents have cost zero for all chores is identically ordered.
- additive_coloring_bound_by_degreeLet G = (V, E) be a finite simple graph, and let a : V → ℕ assign a positive integer to each vertex. Then there exists an additive…
- condorcet_subset_potential_of_integer_slackFor any family of challenger claims with nonnegative integer weights and an integer-valued subset function, suppose every…
- op_258_sum_ne_top_of_forces_threeIf a positive antitone profile a forces a monochromatic triangle K_3 on sufficiently large complete graphs, then the infinite sum of a_i…
- has_ordered_copyAn ordered graph G contains an ordered copy of an ordered graph H if there exists a strictly monotone map f from the vertex set of H to…
- nonsustainable_star_connectivity_of_ascent_stepIf every non-sustainable tree on Fin n (n ≥ 2) that is not a star has a non-sustainable generalized-tree-shift successor with strictly…
- cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core_a10One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core: under the layer-free tight-cover…
- mondrian_two_chain_lower_sum_ltIf C>0, r≥2 and p>r+1, the sum of any finite set of numbers from the chains C*p^a and C*r*p^a that are smaller than a fixed chain element…
- binary_partial_word_partition_order_convexIn a finite Boolean cube partition with one more part than mentioned coordinates, linearly order the parts so that every false occurrence…
- 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).
- wild_three_uniform_fixed_support_disjoint_countFor a finite indexed family T_i of three-element sets and a fixed three-element set S, assume each vertex of S occurs in d indices and…
- circulant_mixed_graph_valid_and_regularFor z ≥ 1 and g ≥ 3, the circulant mixed graph on N = N(z, g) vertices with antipodal edges of jump m = N/2 and arc jumps 1..⌈z/2⌉ and…
- simple_graph_cycle_power_seven_cover_four_tight_dvdA tight cover of C_n^7 (n ≥ 22) by 4 equivalence subgraphs (every distance-7, 6, 4 pair covered exactly once, every class spanned by a…
- cycle_power_fifteen_tight_type_sequence_six_iff_seven_core_a00One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_six_iff_seven_core: under the layer-free tight-cover…
- ErrorCorrectingCodes.Codeword.list_decoding_capacityList-decoding over a q-ary alphabet. Let $\alpha$ be a finite field, write $q = \abs{\alpha}$ for the number of its elements, and fix a…
- KnapsackAuction.feasibleBinaryAllocations_nonemptyKnapsackAuction.feasibleBinaryAllocations_nonempty
- GameTree.IsSubgamePerfect.toSubgamePerfectOnA global subgame-perfect equilibrium is subgame-perfect on every fixed root.
- moebius_odd_squarefree_identity_odd_prime_powFor any prime natural number $p$ with $p \neq 2$ and any natural number $a$, the sum of the Möbius function $\mu(k)$ over all divisors $k$…
- 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…
- ejr_two_voters_criterionFor two voters, a committee W of size k satisfies EJR whenever: (1) if k ≤ |A 0 ∩ A 1| then W ⊆ A 0 ∩ A 1; (2) if |A 0 ∩ A 1| ≤ k then A 0…
- FieldStatistic.ofFinset_insertFieldStatistic.ofFinset_insert
- cycle_power_fifteen_tight_type_sequence_two_iff_three_core_a100001One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_two_iff_three_core: under the layer-free tight-cover…
- WickContraction.finset_eq_fstFieldOfContract_sndFieldOfContractWickContraction.finset_eq_fstFieldOfContract_sndFieldOfContract
- simple_graph_cycle_power_seven_cover_four_tightIn any cover of C_n^7 (n ≥ 22) by 4 equivalence subgraphs, every pair at distance 7, 6 or 4 is covered by exactly one layer, and every…
- prioritized_borel_lex_profiles_prefix_stabilizeEvery lexicographically nondecreasing sequence of infinite binary profiles eventually stabilizes on each finite prefix.
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - cycle_power_fifteen_tight_type_sequence_two_iff_three_core_a1100One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_two_iff_three_core: under the layer-free tight-cover…
- tarski_slice_subbox_monotone_and_fixedFor any monotone map f on [a, b] in dimension k+1 and any coordinate cut c with a_i <= c <= b_i, the sliced map g y j = f (insertNth i c…
- simple_graph_multi_radio_number_path_le_eight_mulFor n, m >= 1 the (m,3)-radio number of the path P_n is at most 8m - 1.
- leviCivitaSymbol_eq_prod_prod_IoiOn
Fin nthe Levi-Civita symbol is the product over pairsi < jof the sign ofg j - g i. Unlike the determinant defining… - integer_atom_sum_bound_of_two_primitive_raysIn an additive subgroup of finite integer vectors, an element with no proper nonzero nonnegative subgroup subvector has coordinate sum at…
- one_layered_linear_boundFor all integers r ≥ 1 and m ≥ r, the maximum number of layers F(m, r) in a 1-layered family of r-subsets on at most m vertices satisfies…
- prioritized_borel_lex_profile_le_limitEach member of a lexicographically nondecreasing binary profile sequence is at most its coordinatewise limit.
- cycle_power_fifteen_tight_type_sequence_two_iff_three_core_a001One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_two_iff_three_core: under the layer-free tight-cover…
- postage_stamp_number_three_eight_eqThe classical postage stamp number with four stamps (one of them 0) and h = 8: n_8(3) = 89, attained by {0, 1, 9, 14}.
- postage_stamp_number_neg_two_eq_of_mod_four_eq_twoIf h ≥ 2 and h ≡ 2 (mod 4), then n♭_h(2) = n_h(2) = (h² + 6h)/4.
- picking_prefix_state_allocated_card_leAfter s turns of a picking sequence at most s items have been allocated: every picking_turn inserts at most one item into the allocated set.
- exists_not_near_regular_tournament_fourThere exists a tournament on 4 vertices that is not near-regular.
- simple_graph_path_graph_walk_length_geEvery walk in the path graph P_n from u to v has length at least |u - v|.
- has_ordered_copy_selfEvery ordered graph contains an ordered copy of itself via the identity map.
- one_layered_binomial_bound_le_powerFor integers r ≥ 1 and m ≥ r, the binomial bound (m - r + 1) * choose(⌊log_2(m - r + 1)⌋ + r - 1, r - 1) is at most (m - r + 1)^(1 + log_2…
- postage_stamp_basis_range_neg_ge_of_mod_twelve_eq_nineFor h = 12r + 9, the set {-(2r+2), 2r+2, 4r+5} (which contains a negative integer) has h-range at least ⌊(h²+6h+1)/4⌋ - 1 = n_h(2) - 1.
- uniformDistributionThe uniform distribution $U_k$ on $\{1, \dots, k\}$, viewed as a function on $\mathbb{N}^+$, evaluates to $1/k$ for $n \le k$ and $0$ for…
- condorcet_acyclic_half_cover_signature_pairs_ge_sevenLet a relation on Fin m have an outside common predecessor for every set of at most three vertices, and let a positive finite family of…
- circulant_mixed_graph_cycle_g_existsFor z ≥ 1 and g ≥ 3, the circulant mixed graph on N(z, g) vertices has a mixed cycle of length g: when z is even, g - 1 arc steps of jump…
- simple_graph_cycle_power_seven_layer_weight_eq_class_five_imp_one_two_imp_sixLet c label the vertices of C_n^7 (n ≥ 22) so that every label class is a clique, with total weight Σ_i (2·[i ~ i+7] + [i ~ i+6] + [i ~…
- four_point_positive_kernel_primitive_boundary_decompositionFor two integer rows on four coordinates with independent first two columns and a strictly positive integer common kernel vector x, there…
- ejr_greedy_cohesive_pair_auxFor every voter subset S and positive committee parameter K, a greedy cohesive core W has cost at most |S|K/n and satisfies every…
- SocialChoice.Voting.prefers_transSocialChoice.Voting.prefers_trans
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_a01000One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- 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…
- odd_squarefree_indicator_oneThe odd square-free indicator of $1$ is equal to $1$.
- target_prefix_capacity_eq_populationFor any natural number n, population vector y in stdSimplex ℝ (Fin n), Gibbs vector γ in stdSimplex ℝ (Fin n) with strictly positive…
- grid_arrangement_column_deviation_subset_sum_boundLet $n \ge 3$, $N = n^2$, and let $S : \mathrm{Fin}\ n \times \mathrm{Fin}\ n \to \mathbb{Z}$ be an injective arrangement with entries in…
- independent_rank_trajectories_single_goodFor n ≥ 2 agents and m = 1 good, under any length-1 picking sequence, the agents' received rank vectors are mutually independent under…
- zero_sum_w_three_threew_3(3) = 13: every admissible sequence (no term ≡ 0 mod 3) of 13 vectors in ℤ^3 has a nonempty subsequence whose sum is ≡ 0 (mod 3) but ≢…
- g_add_dimsAdditive dimension identity for an isotropic subspace. Let $S$ be an isotropic submodule of the symplectic space…
- SocialChoice.FairDivision.Divisible.ds_oneBase case: 1 agent receives the whole cake. Proportionality holds trivially on the whole unit interval.
- 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…
- round_robin_pne_envy_zero_ef1_of_deviation_certificateIf the deviation certificate of round_robin_two_mul_add_one_deviation_certificate holds for agent i ≠ 0, then at a pure Nash equilibrium…
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_a00001100000One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- 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…
- Fin.fst_ne_succSuccAbove_preFin.fst_ne_succSuccAbove_pre
- op223_example_graph_edge_01_sustainableEdge 0-1 in op223_example_graph is sustainable.
- cycle_power_fifteen_tight_type_sequence_four_iff_five_core_b01One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_four_iff_five_core: under the layer-free tight-cover…
- perm_inflection_set_eq_two_of_sign_patternIf a permutation σ has discrete second derivative that is non-negative on [2, k₁), positive at k₁, zero on (k₁, m₁), negative at m₁,…
- davenport_box_three_odd_sequence_sumThe sequence T(m) (odd case) is a zero-sum sequence, for every m ≥ 2.
- card_filter_lt_card_filter_of_ltFor f : α → β with β linearly ordered and α finite, if f a < f b then strictly fewer elements of α have f-value below f a than below f b.
- ordered_ramsey_monotone_cycle_three_alternating_path_threeThe ordered Ramsey number of the monotone cycle MC_3 and the alternating path AP_3 is equal to 5.
- comparison_eval_ker_le_span_kappaEvery formal quadratic feature vector c in F_2 that evaluates to zero on every strict order (<phi_2(x), c> = 0 for all permutations x of…
- postage_stamp_number_three_eight_lt_negWith four stamps and h = 8, allowing a negative denomination strictly helps: n_8(3) = 89 < 99 ≤ n♭_8(3). (For three stamps the opposite…
- condorcet_subset_potential_of_cardinality_slackFor a finite family of weighted challenger claims, suppose an integer potential has local removal deficit bounded by an arbitrary integer…
- op869_double_countDouble counting in a bipartite incidence: if every element x of A meets at least d elements of B, then for i ≤ |A|, |A|·d ≤ |B|·(i-1) +…
- 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.
- carpool_witness_familyFix n, T, an edge sequence (u_t, v_t) and D >= 300. From the edges alone one builds a family W of pairs (t, S) with |W| <= 2 T…
- KnapsackAuction.PositiveWeightsEvery public weight is strictly positive.
- dedekind_number_zeroThe 0-th Dedekind number is 2.
- signed_graph_reconstructible_balanced_mono_invariantA connected balanced signed graph is reconstructible from its switching deck if its underlying graph has an automorphism-invariant vertex…
- carpool_backward_step_slack_increaseFor natural numbers n and T, an integer D, trajectory d : ℕ → Fin n → ℤ, and receiver/sender functions a, b : ℕ → Fin n satisfying for all…
- fin_intervals_intersection_nonempty_of_pairwise_interLet L be a natural number and let ι be a finite nonempty index type. Let [a i, b i] for i : ι be a family of nonempty closed intervals in…
- mu_star_oneThe natural number 1 satisfies mu_star.
- simple_graph_cycle_power_dyadic_cover_tight_long_edgesIn an m+1-layer equivalence cover at dyadic bandwidth, every endpoint-distance edge and every other positively weighted dyadic long edge…
- Bornology.IsBounded.continuous_sInfSimilar to
IsCompact.continuous_sInf, but taking a bounded set in the bornology instead of a compact set. - Matrix.diag_pow_entry_eq_pow_diag_entryFor an upper–triangular matrix
A, the(i,i)entry of the powerA ^ nis simply then-th power of the original diagonal entry. - postage_stamp_number_neg_two_of_odd_decompEvery 3-element set of integers with a negative element is {a, a+x, a+y} with a < 0 < x < y.
- Pref.ofTotalPreorderBundle an explicit total preorder as a preference.
- tournament_of_symm_matrix_is_tournamentT(G) is a tournament for every matrix G over F₂ (only the entries above the diagonal are read).
- energy_filter_centered_binomial_tsum4_to_rowFor any real integer sequence and k, the four-index centered-binomial weighted cycle sum equals the original fourfold binomial row sum…
- cycle_power_fifteen_tight_type_sequence_two_iff_three_core_a0001001One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_two_iff_three_core: under the layer-free tight-cover…
- KnapsackAuction.fractionalFeasibleFeasibility of a fractional knapsack allocation: pointwise fractions lie in
[0,1]and the weighted load respects capacity. - mondrian_prime_square_area_middle_shape_boundFor distinct primes p and q and t+r=2e with positive r, at most r unordered shapes of area q^2 times p^t fitting in a q times p^e square…
- Fin.succSuccAbove_lt_iff_ltFin.succSuccAbove_lt_iff_lt
- cycle_power_fifteen_tight_type_sequence_two_iff_three_core_a0000One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_two_iff_three_core: under the layer-free tight-cover…
- cycle_power_fifteen_tight_type_sequence_six_iff_seven_core_b00001One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_six_iff_seven_core: under the layer-free tight-cover…
- antitone_mul_of_antitone_nonnegThe product of nonneg antitone sequences is antitone.
- op_153_positive_quadratic_eventually_strict_monoA degree-2 integer polynomial taking positive values on all positive integers has positive leading coefficient and is eventually strictly…
- nat_scaled_floor_ltFor positive natural n and N, and natural i less than n, floor(i*N/n) is less than N.
- GameTree.StrategyA pure strategy for the entire game tree: at every possible node context
(mover, head, tail), specify one child (bundled with its… - cycle_link_zero_crosses_cutFor integers v, a, b, n satisfying 0 < v < n and 1 ≤ a ≤ v ≤ b < n, the candidate link (0, v) crosses the cycle cut [a, b], that is, (a ≤…
- ejr_of_support_density_boundFor a nonempty electorate, the density bound with q=k+1 implies EJR for any committee of size k.
- petersen_strip_witness_cardFor each natural number k ≥ 8, the witness set petersen_strip_witness k has cardinality k^2/2 + 1.
- consecutive_sum_ne_mul_prime_of_two_mul_ltIf p is a prime with p > 2n and a ≥ 1, then a·p is not a sum of one or more consecutive integers from {1, …, n}.
- VNM.NotTransitive.independentVNM.NotTransitive.independent
- cycle_power_fifteen_tight_type_sequence_twelve_iff_thirteen_core_b01One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_twelve_iff_thirteen_core: under the layer-free…
- VNM.NotComplete.continuousVNM.NotComplete.continuous
- satisfies_geodetic_product_condition_const_oneFor any diameter d and any bound K ≥ 1, the constant sequence c = 1 satisfies the geodesic product condition for K.
- postage_stamp_number_neg_two_of_odd_cases_threeFor h = 2m+1 with m ≡ 29 (mod 30): no coprime x < y and a < 0 satisfy the Theorem 4.1 inequalities at range m² + 4m - 1 = n_h(2) - 3.
- cycle_power_fifteen_tight_type_sequence_ten_iff_eleven_core_a1One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_ten_iff_eleven_core: under the layer-free tight-cover…
- comparison_phi1_linearIndependentThe constant function 1 and the comparison signs d_e, e an edge of [n], are linearly independent real functions on strict orders…
- cycle_power_fifteen_tight_type_sequence_two_iff_three_core_a00011One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_two_iff_three_core: under the layer-free tight-cover…
- FieldStatistic.ofFinsetThe field statistic associated with a map
f : Fin n → 𝓕(usually.getof a list) and a finite set of elements ofFin n. - cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_b01One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- op_193_cycle_isolated_vertex_chromatic_leFor any natural numbers k ≥ 3 and m ≥ 4 * k - 3, the chromatic number of the G-stable Kneser graph of the disjoint sum of the m-cycle and…
- cycle_power_fifteen_tight_type_sequence_one_alternates_core_alt111010One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_alternates_core: under the layer-free tight-cover…
- IntervalFamilyAn interval family for a colored tree consists of an injective mapping from vertices to integers and a laminar family of non-empty integer…
- cycle_power_fifteen_tight_type_sequence_six_iff_seven_core_a01One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_six_iff_seven_core: under the layer-free tight-cover…
- low_hole_reduction_overtakeLet m, n be natural numbers and let z, z_RL, z_2, z_2A, H, d be integers. If z_RL ≤ z_2, z_2 ≤ z_2A, 0 ≤ H, 0 ≤ d, 2 * (z_2A - z_RL) =…
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_a00001101One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- cycle_power_fifteen_tight_type_sequence_shape_rules_core_v60_71Window refutation for k = 15: in the layer-free tight-class model on the integer line (x p j: the class starting at p contains p + j;…
- IsPositiveAffineOf.reflPositive affine transformation is reflexive (identity: a=1, b=0).
- with_top_nat_lex_add_binary_le_iffPointwise addition of a binary shift sequence e : ℕ → {0, 1} strictly preserves and reflects the lexicographic order on WithTop ℕ streams.
- mondrian_divisors_card_le_two_mul_of_le_sqAn integer D at most c squared has at most 2c positive divisors.
- IsPositiveAffineOf.symmPositive affine transformation is symmetric (invertible). [MSZ Ex 2.19] If
v(x) = a·u(x) + bwitha > 0, then… - Matrix.schurTriangulationAuxThis is
LinearMap.SchurTriangulationAuxadapted for matrices in the Euclidean space. - girth_parent_charge_weight_boundA charged subset of m parents satisfying the girth-dependent proper-subset condition has the displayed weighted parent-plus-charge bound.
- cycle_power_fifteen_tight_type_sequence_two_iff_three_core_b0One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_two_iff_three_core: under the layer-free tight-cover…
- biased_bit_vulnerability_ge_one_sub_mul_momentFor 1/2 < p < 1 and any probability distribution q on ℤ with finite absolute first moment, the one-guess vulnerability satisfies V_p(q) ≥…
- GameTree.IsNashEquilibriumNash equilibrium: no single player can improve their outcome at the root game by unilateral deviation. Weaker than
IsSubgamePerfect,… - op744_dice3_no_cycle_threeThe relation (dice_graph 3).Adj contains no directed simple cycle of length 3, that is, ¬ has_directed_cycle (dice_graph 3).Adj 3.
- two_ray_nonnegative_sum_boundFor finite integer-valued functions u,v,x and natural D,a,b with D positive and a+b at most D, if D*x=a*u+b*v coordinatewise and both u…
- cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core_a01110One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core: under the layer-free tight-cover…
- cycle_power_dyadic_int_weight_le_cardFor a finite integer set of diameter at most 2^m-1, weight its endpoint-distance pairs by two and its other dyadic long-distance pairs by…
- has_contiguous_subtreesAn interval family has contiguous subtrees if the identifier image of every subtree is a closed integer interval.
- quadratic_comparison_evaluation_kernel_and_projectorLet n >= 3, N = C(n,2), nu_triangle = C(n,3). Strict orders on [n] are given by permutations x of Fin n (x i = rank of label i); for an…
- cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core_b01One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core: under the layer-free tight-cover…
- cycle_power_fifteen_tight_type_sequence_twelve_iff_thirteen_core_b001One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_twelve_iff_thirteen_core: under the layer-free…
- 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)) -…
- GameTree.optStrategyThe canonical backward-induction strategy: at each node, pick a child whose backward-induction value equals the node's value (i.e., a…
- cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core_b1110One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core: under the layer-free tight-cover…
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_a0001One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- tournament_exists_decycling_familyEvery finite tournament can be made acyclic by finitely many inversions (so its inversion number is attained).
- IntervalPosetAn interval-poset is a strict partial order on a linearly ordered set satisfying the Tamari convexity conditions: if a < b < c and a ≺ c…
- rank_score_veto_core_distance_monoIn a pseudometric space on V ⊕ C consistent with prof, if candidate x is weakly better than y for voter v then v is weakly closer to y…
- postage_stamp_number_neg_two_of_odd_family_2For m ≥ 5 with m ≡ 5 (mod 6) and m ≢ 4 (mod 5), the set {-2, 3, m-1} (2m+1)-fold covers [0, m² + 4m - 1] = [0, n_h(2) - 3].
- postage_stamp_basis_range_zero_one_ge_of_mod_four_eq_twoFor h = 4w - 2 (w ≥ 1), the basis {0, 1, 2w} = {0, 1, (h+2)/2} has h-range at least (w+1)h = (h² + 6h)/4: every integer in [0, (w+1)h] is…
- Fin.succSuccAbove_commFin.succSuccAbove_comm
- comparison_tree_eval_bindRunning the composition
comparison_tree_bind T fon a value assignmentvgives the same index as runningTonvand then running… - VNM.NotTransitive.continuousVNM.NotTransitive.continuous
- sumset_rep_support_and_symmetryLet k ≥ 3, h ≥ 2, and q ≥ k be integers. Then sumset_dot_product_set h k q = Finset.Icc ((h : ℤ) + 1) (((h : ℤ) + 1) * (q : ℤ)), its…
- sustainable_path_connectivity_of_descent_stepIf every sustainable tree on Fin n (n ≥ 1) that is not a path has a sustainable generalized-tree-shift predecessor with strictly smaller…
- forward_biased_selector_dominating_and_computableOn every Markov paging instance with n pages, cache C, fault on page s, and hitting probabilities α, assuming the dominating distribution…
- GameTree.outcomeThe outcome (terminal payoff vector) of playing strategy
σstarting from game treeg. Walks down the tree, usingσto pick a child… - cycle_power_fifteen_tight_type_sequence_two_iff_three_core_a1000000One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_two_iff_three_core: under the layer-free tight-cover…
- exists_rank_one_mic_with_invertible_dualFor every natural number d ≥ 2 there exist g : Fin (d ^ 2) → Fin d → ℂ, real-linear functionals c : Fin (d ^ 2) → (Matrix (Fin d) (Fin d)…
- prioritized_borel_lex_strict_changes_infinite_limitIf a lexicographically nondecreasing sequence of binary profiles has strict increases arbitrarily late, its coordinatewise limit contains…
- WiringDiagramPairAn instance of the zero excess problem consisting of a wire count m and two rank-3 signotopes u and v on Fin m representing wiring…
- int_mem_h_fold_sumset_le_of_forall_leIf every element of A is at most b, every element of hA is at most h·b.
- arrangement3_diophantine_systemFor integers $\kappa, a', c', \xi', \eta'$ satisfying $\xi' + \eta' = \kappa$, $4\kappa^2 + 3(a'^2 + c'^2) + \xi'^2 + \eta'^2 = 30$, and…
- cycle_power_inflation_parametersFor natural k at least one and natural n at least both 2*k+2 and 2*k squared, put q=floor((n+k)/(k+1)). Then q is at least two, n is at…
- 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).
- PositiveRealUnitCore.div_ne_zeroPositiveRealUnitCore.div_ne_zero
- cycle_power_fifteen_tight_type_sequence_six_iff_seven_core_a111100One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_six_iff_seven_core: under the layer-free tight-cover…
- cycle_power_fifteen_tight_type_sequence_six_iff_seven_core_b101One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_six_iff_seven_core: under the layer-free tight-cover…
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_b1One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- op_258_forces_of_capacity_lt_oneIf k ≥ 2 and Σ_i min(a_i, 1 - 1/(k-1)) < 1, then every a-bounded colouring of K_n for large n already contains a monochromatic K_k; i.e. a…
- postage_stamp_number_neg_two_of_odd_upper_fourFor odd h ≥ 5 with h ≡ 59 (mod 60), every 3-element set with a negative element has h-range at most n_h(2) - 4.
- tournament_not_near_regular_exists_arc_degree_gapIn a tournament on 2m vertices with m ≥ 2 that is not near-regular, there are vertices u, v with an arc u → v and out-degree of v at least…
- digraph_apex_over_bidirected_complete_min_cut_leFor every vertex set A of D_d, min(e(A, Aᶜ), e(Aᶜ, A)) ≤ ⌊(d + 1)²/4⌋.
- arrangement3_e4_zero_of_is_magicEvery magic square of order 3 satisfies the four-term line-sum energy zero condition $E_4(S) = 0$.
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_a0000110000111One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- mondrian_no_perfect_prime_mul_prime_powFor every pair of distinct primes p and q and every natural exponent e, the square of side q times p^e has no perfect admissible integer…
- postage_stamp_basis_range_add_two_le_of_neg_of_oddFor odd h ≥ 5 with h ≢ 9 (mod 12), every 3-element set of integers containing a negative integer has h-range at most n_h(2) - 2 =…
- midpoint_certificate_matrix_minor_abs_leThe absolute value of every k x k minor of a (k+1) x (k+1) midpoint-certificate matrix is bounded by 2^k, proved by multilinear expansion…
- boolean_influence_le_oneFor any finite type $U$ with decidable equality, monotone Boolean function $f : (U \to \mathrm{Bool}) \to \mathrm{Bool}$, coordinate…
- postage_stamp_basis_range_zero_one_ge_of_oddFor odd h = 2m + 1, Stöhr's extremal basis {0, 1, (h+3)/2} = {0, 1, m+2} has h-range at least m² + 4m + 2 = (h² + 6h + 1)/4: every integer…
- KnapsackAuction.fractionalGreedyListGreedy fractional allocation along a fixed list order. If the next item does not fully fit, the algorithm takes exactly the remaining…
- prioritized_borel_lex_profiles_limitA lexicographically nondecreasing sequence of infinite binary profiles has a coordinatewise limit, with uniform eventual agreement on each…
- op_517_zero_excess_of_eqEvery rank-3 signotope on Fin m has braid-move excess 0 with respect to itself: the distance in B(m, 2) from u to u is 0, which equals the…
- int_crescent_point_boundFor every integer n ≥ 3, every index j in Fin n, and every coordinate index i in Fin 3, the absolute value of the i-th coordinate of…
- Matrix.exp_series_diag_term_eqEach term in the matrix exponential series equals the corresponding scalar term on the diagonal
- KnapsackAuction.RespectsCapacityThe allocation rule respects the knapsack capacity constraint.
- PositiveRealUnitCore.div_posPositiveRealUnitCore.div_pos
- deadline_schedule_exists_iff_sorted_deadline_geBoxes i₁, …, i_k with nondecreasing integer deadlines d_{i₁} ≤ … ≤ d_{i_k} can be opened one per round (rounds 1, 2, …), each box i in a…
- Fin.succSuccAbove_natAdd_apply_castAddFin.succSuccAbove_natAdd_apply_castAdd
- WickContraction.fstFieldOfContractThe smallest of the two positions in a contracted pair given a Wick contraction.
- fin_triplesThe list of all ordered triples (a, b, c) of elements of Fin m satisfying a < b < c.
- Bornology.IsBounded.continuous_iSupBornology.IsBounded.continuous_iSup
- as_dt_path_intersection_le_twoFor any natural number n and any coordinate functions a1 and a2 satisfying IsASPath, the intersection of asTrace n a1 and dtTrace n a2 has…
- KnapsackAuction.sortedAgentsByRatioAgents sorted by decreasing value-to-weight ratio, with lexicographic tie-breaking via the ambient order on
I. - wiring_diagram_pair_encodeEncodes an instance of a pair of wiring diagrams on m pseudolines as a list of Booleans consisting of m unary ones followed by false and…
- GameTree.value_optStrategy_eqAt a node, the
optStrategypicks a child whose value equals the node's value. - dyadic_spectral_series_boundLet a ≥ 0, and let mu : ℕ+ → ℝ be a non-negative sequence satisfying ∑' j, mu j ≤ 1 and tail bounds ∑_{k > j} mu k ≤ (1/2)^j for all j ≥…
- GameTree.Kuhn_exists_SPEKuhn's theorem (existence form): every finite perfect-information game without chance admits a subgame-perfect equilibrium. The…
- Bornology.IsBounded.continuous_iInfBornology.IsBounded.continuous_iInf
- forest_greedy_envelope_preserved_by_independent_mergeIndependent symmetric finite uniform discrepancy laws of fixed parity that satisfy the envelope still satisfy it after one greedy step…
- forest_greedy_high_tail_stepFor two independent nonempty finite uniform integer laws and a fair tie coin, the updated tail at k is at most the first tail at k+1 plus…
- op_258_bounded_extensionFor a positive antitone profile a with Σ a i > 1 there is n₀ such that for every n ≥ n₀, every partially defined a-bounded colouring of…
- int_box_extremal_sequence_countsIf integers A, B, C with 0 ≤ C ≤ M(2M−1) satisfy A·(M, M) + B·(−M, M−1) + C·(M−Q, −M) = 0, where M ≥ 2, gcd(M, Q) = 1 and gcd(2M−1, 2M−Q)…
- forest_greedy_refined_tail_stepFor two independent uniform finite integer laws and a fair tie coin, the probability that a greedy update reaches threshold k is bounded…
- davenport_box_three_odd_sequence_minimalFor m ≥ 2 odd, T(m) is a minimal zero-sum sequence: no proper nonempty subsequence sums to zero.
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_a00001100001100001One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- GameTree.mem_valueList_iffMembership in
valueListvia membership in the source list. - cycle_power_fifteen_tight_type_sequence_one_alternates_core_alt00000100_p3Sub-branch of the window refutation cycle_power_fifteen_tight_type_sequence_one_alternates_core_alt00000100 (one subtree of its case…
- monotoneMixtureWeight_sum_by_partsFor any sequence $P : \mathbb{N}^+ \to \mathbb{R}$ and any $n \in \mathbb{N}^+, the finite sum of mixture weights satisfies $\sum_{k=1}^n…
- SocialChoice.FairDivision.Divisible.chooser_isEnvyFreeThe chooser (agent 1) never envies the cutter, regardless of the cut point. Since agent 1 selects whichever piece they value more,…
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_a000011001One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- GameTree.IsSubgamePerfect.toNESPE ⇒ NE: every subgame-perfect equilibrium is a Nash equilibrium (at any fixed root game).
- op_258_one_le_tsum_of_boundedLet n ≥ 2, let a : ℕ+ → ℝ and let c be an a-bounded colouring of the edges of K_n. Then the ENNReal-sum of the a i is at least 1.
- KnapsackAuction.NonnegativeCapacityThe knapsack capacity is nonnegative.
- LinearMap.BilinForm.continuous_iSupAlias of
LinearMap.continuous_iSup'that takesLinearMap.BilinForm. - efx_three_pair_anchor_sanityThe starting allocation is envy-free with r+2 goods per bundle and one charity good; the lifted complete witness is EFX.
- postage_stamp_basis_range_ge_of_mod_four_eq_zeroFor h = 4w with w ≥ 2, the set A = {−(w − 1), w, w + 2} satisfies n_h(A) ≥ w(4w + 6) = (h² + 6h)/4.
- Matrix.schurTriangulationThe upper triangular form induced by
A.schurTriangulationUnitaryto which a matrixAover an algebraically closed field is unitarily… - has_induced_k4_subdivision_topThe complete graph on four vertices contains an induced subdivision of K4, using the six single-edge paths.
- cycle_power_fifteen_tight_type_sequence_two_iff_three_core_a0001000One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_two_iff_three_core: under the layer-free tight-cover…
- wild_number_complete_graph_upper_sub_four_add_parityFor every integer n>=13, every natural number k equal to the chromatic number of the line graph of K_n, and every proper edge coloring c…
- cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core_a010100000One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_eight_iff_nine_core: under the layer-free tight-cover…
- simple_graph_equivalence_covering_number_cycle_power_dvdFor k ≥ 1 and q ≥ 2, the k-th power of the cycle on q(k + 1) vertices has equivalence covering number exactly 1 + ⌈log₂(k + 1)⌉.
- additive_sum_le_of_two_bundles_coverTwo-deviation certificate: if two bundles D1, D2, each worth at most v(A) to an agent with nonnegative additive values, together cover…
- davenport_box_three_odd_sequence_cardThe sequence T(m) (odd case) has length 16m^3 - 16m^2 + 10m - 2.
- wiring_diagram_zero_excessA pair of wiring diagrams (represented as rank-3 signotopes) has braid-move excess 0 if their distance in the higher Bruhat graph B(m, 2)…
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_a0000110000110One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- digraph_nonneighborhood_kernels_weighted_half_coverIn a finite loopless oriented graph in which the induced non-neighborhood of every vertex has an out-kernel, every nonnegative integer…
- jl_union_boundUnion bound for Johnson–Lindenstrauss distortion. Let $(\Omega,\mu)$ be a probability space, and let $A\colon\Omega\to\bbr^{k\times d}$ be…
- q_ary_subsequence_num_embeddingsFor words u of length m and w of length n over an alphabet of size q represented by Fin q, q_ary_subsequence_num_embeddings q m n u w is…
- List.le_argMaxOn_headThe argmax achieves at least the head's value.
- prioritized_borel_finite_hidden_opponent_choices_positionalFix a winning strategy in a prioritized tree game, with an arbitrary state type. Suppose that on every legal play, all but finitely many…
- block_insertion_residual_cost_boundGiven a type α with decidable equality, a cost function c : α → NNReal, a natural number k : ℕ with 1 ≤ k, a bundle B : Finset α with k ≤…
- condorcet_ordering_score_le_subset_potentialFor any finite family of challenger claims and nonnegative integer claim weights, suppose a natural-valued potential on remaining…
- KnapsackAuction.maximalSocialWelfareThe maximal social welfare over the feasible binary allocation space.
- davenport_constant_support_four_int_box_three_ge_evenTheorem 3 of arXiv:2610.16562, even m: for every even m ≥ 2, the maximal length of a minimal zero-sum sequence over [[-m,m]]^3 with…
- tarski_query_complexity_le_polylogMultidimensional Tarski search is polylogarithmic: for every fixed k there is a constant C with Tarski(n,k) ≤ C·(log₂ n + 2)^k for all n ≥…
- List.foldl_max_ge
foldl_max_ge: every element'sf-image is≤that of the running maximizer kept by the left fold. The induction generalizes the… - open_problem_line_cubic_t_countFor every integer n ≥ 5, there exists a parity representation of the line cubic syndrome of cardinality 2n + 1.
- ejr_support_density_bound_emptyEvery approval profile satisfies the initial density bound q=1 at the empty committee.
- cycle_power_fifteen_tight_type_sequence_two_iff_three_core_a01One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_two_iff_three_core: under the layer-free tight-cover…
- LinearMap.continuous_iInf'A specialization of
LinearMap.continuous_iInfto finite dimensional spaces, in place of requiring a (non-instance)IsModuleTopology. - path_three_radio_labeling_span_ge_sevenFor n >= 8, every (1,3)-radio labeling of the path P_n has span at least 7; combined with the upper bound 8m-1 at m = 1 this gives that…
- positive_binary_identity_bound_of_perm_coverLet k ≥ 1 be an integer, and let C be a finite set of natural numbers covering the element orders of Equiv.Perm (Fin k) (satisfying…
- cycle_power_fifteen_tight_type_sequence_six_iff_seven_core_b1001One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_six_iff_seven_core: under the layer-free tight-cover…
- cycle_power_fifteen_tight_type_sequence_shape_rules_core_v40_51Window refutation for k = 15: in the layer-free tight-class model on the integer line (x p j: the class starting at p contains p + j;…
- decay_ramsey_density_classA sequence a : ℕ+ → ℝ belongs to the class decay_ramsey_density_class if every term a i > 0, a is antitone, and the sum in ℝ≥0∞ satisfies…
- cycle_power_fifteen_tight_type_sequence_shape_rules_core_v50_61Window refutation for k = 15: in the layer-free tight-class model on the integer line (x p j: the class starting at p contains p + j;…
- 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…
- VNM.sure_thing_principleThe Sure-Thing Principle [MSZ Ex 2.12]: The common lottery in a mixture does not affect strict preference. If Independence holds, then…
- pgroup_coordinate_orbit_orderhom_card_modLet p be prime, G a p-subgroup of the permutations of Fin n acting by coordinate permutations on the n-fold product of the finite chain…
- prioritized_borel_reverse_deterministic_finite_hidden_priorities_positionalConsider a prioritized tree game. Assume that any two legal edges at the same source node with the same direction and target state have…
- DieThe type of non-standard n-sided dice with face values in Fin n, represented as non-decreasing functions from Fin n to Fin n.
- mondrian_prime_shape_boundIf k times A is the area of a c times p to the e square and p exceeds c, at most c * (v_p(k) + 1) unordered shapes of area A fit in the…
- postage_stamp_number_neg_two_of_odd_boundsIf {a, a+x, a+y} (a < 0 < x < y) h-fold covers [0, R] with h = 2m+1 and R ≥ 2m+2, then x, y are coprime and (y-1)(1-x) ≥ ha ≥ R - (2m+2)y…
- SocialChoice.FairDivision.Divisible.DubinsSpanierPropThe inductive predicate for the Dubins–Spanier algorithm: for n agents indexed by
Fin n, a complete proportional allocation exists. - KnapsackAuction.zeroBinaryRespectsCapacityKnapsackAuction.zeroBinaryRespectsCapacity
- tarski_box_query_le_smallBrute force on small boxes: if every box in dimension k has at most M points, then every box query is answerable within M queries — and in…
- IsRiskNeutral.isAffineRisk neutrality implies affine utility. [MSZ 2.27, hard direction] Requires
|I| ≥ 2so that non-trivial distributions exist. - energy_filter_centered_kernel_step_integralFor k≥1 and integer shifts u,v,w, the integral of the four shifted binomial weights at floor(√k x) equals their integer sum divided by √k.
- two_deletion_num_embeddingsFor a binary word w of length n and y of length n + 2, two_deletion_num_embeddings n w y is the number of strictly increasing index…
- hypercube_d_convex_iff_majority_closed_and_has_relative_opposite_pairLet X : Finset (Fin n → Bool) be a nonempty finite subset of vertices of the unit hypercube. Then X is D-convex (hypercube_is_d_convex X)…
- boolean_derivative_bent_dim_eight_is_balancedFor every bent function g on (Fin 8 → ZMod 2) and every nonzero vector v, the directional derivative of g along v is balanced.
- cycle_power_fifteen_tight_type_sequence_ten_iff_eleven_core_b1110One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_ten_iff_eleven_core: under the layer-free tight-cover…
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_b00000One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- 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…
- FieldStatistic.ofFinset_finset_mapFieldStatistic.ofFinset_finset_map
- op744_dice7_has_cycle_fourteenThe relation (dice_graph 7).Adj has a directed simple cycle of length 14, has_directed_cycle (dice_graph 7).Adj 14.
- one_layered_linear_bound_sum_leFor integers r ≥ 2, k ≥ 1, r ≤ m, and S with k * r ≤ S ≤ 2 * m - r, the block sum 2^(r - 2) * (S - k * r) + k is at most 2^(r - 1) * (m -…
- postage_stamp_is_coprime_of_memIf 0 and 1 are both in the h-fold sumset of {a, a+x, a+y} with distinct elements, then x and y are coprime.
- pandora_exists_balancing_thresholdThere is a threshold t >= 0 at which the maximum total capped surplus over deadline-feasible sets equals t, attained by some feasible set.
- Matrix.diag_pow_of_blockTriangular_idFor an upper-triangular matrix, the diagonal of a power is the power of the diagonal.
- tarski_subinterval_fixed_pointSubinterval fixed point theorem: if a monotone map f satisfies a ≤ f(a) and f(b) ≤ b, then f has a fixed point in the sub-box [a, b].
- op_258_forces_of_forces_smul_blowupFor γ ≥ 1 and k ≥ 1: if a forces a monochromatic K_{γk}, then the profile γ·a forces a monochromatic K_k.
- VNM.NotIndependent.continuousVNM.NotIndependent.continuous
- greedy_max_cut_half_edges_lower_boundEvery finite simple graph G has a subset of vertices S such that the number of cut edges between S and V \ S is at least half the total…
- GameTree.isSubgamePerfectOn_iff_forall_subtree_isNashAtRoot-scoped subgame perfection is equivalent to Nash equilibrium at every subtree of the root. This is the pure finite-tree form of MSZ…
- is_intersective_exists_posIf h ∈ ℤ[X] is intersective and m is a positive integer, there exists a positive integer n > 0 such that h(n) ≡ 0 (mod m).
- sumset_rep_count_eq_zero_of_gtFor any k ≥ 1, h, q, and integer s > (h + 1) * q, the representation count ν_q(s) is zero.
- cycle_power_aligned_end_blocks_endpoint_overlapFor nested aligned end-block widths, every class through the last point of a different old class intersects the translated new class one…
- finset_midpoint_balanced_exists_nonzero_minorEvery nonempty midpoint-balanced subset B of ZMod p contains an inclusion-minimal balanced subconfiguration of size k+1 ≤ |B| with k > 0…
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_a1One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- mondrian_two_chain_signed_sum_ne_zeroA nonempty signed sum of distinct numbers drawn from the chains C*p^a and C*r*p^a cannot vanish when C is positive, r≥2 and p>r+1.
- four_point_primitive_boundary_kernel_is_atomFor a rank-two integer matrix on four columns that has a strictly positive common kernel vector, every nonzero nonnegative primitive…
- layered_digraph_compatible_family_common_vertexLet G = (V, E) be a directed graph on a vertex type V, let L be a positive natural number (0 < L), and let layer : V → ℕ be a layer…
- KnapsackAuction.natFractionalGreedyValue_le_integralGreedyValue_plus_highestKnapsackAuction.natFractionalGreedyValue_le_integralGreedyValue_plus_highest
- Fin.predPredAbove_valFin.predPredAbove_val
- Matrix.matrix_exp_series_diag_eq_scalar_seriesThe diagonal of the matrix exponential series equals the scalar exponential series
- is_adj_trace_minimalA graph G on a finite vertex set V is trace-minimal in the class of d-regular graphs if G is d-regular and its adjacency trace sequence is…
- simple_graph_card_low_left_degree_geLet G be a finite graph, k a real with k ≥ 2|E(G)|/|V(G)|, and 0 ≤ q < k. For any ordering σ of the vertices, at least (q/(k+q))·|V(G)|…
- 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,…
- cycle_power_fifteen_tight_type_sequence_twelve_iff_thirteen_core_b1100One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_twelve_iff_thirteen_core: under the layer-free…
- cycle_power_fifteen_tight_type_sequence_two_iff_three_core_b1One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_two_iff_three_core: under the layer-free tight-cover…
- mondrian_prime_first_exponent_shape_boundWhen the p-adic exponent of k is exactly one, at most c unordered shapes of area A fit in a c times p to the e square with area k times A…
- finset_one_inclusion_graph_card_edgeFinset_leIf a finite set system F has VC dimension at most d, its one-inclusion graph has at most d·|F| edges.
- KnapsackAuction.exists_welfareMaximizerA welfare-maximizing feasible binary allocation, chosen using
List.argMaxOnon the finite space of feasible0/1allocations. - postage_stamp_number_two_eqThe classical postage stamp number for three stamps: n_h(2) = ⌊(h² + 6h + 1)/4⌋ for every h ≥ 1.
- is_balanced_scheduleA picking sequence of m turns among n agents is balanced if each complete block of n turns contains each agent exactly once, and the…
- beat_scoreThe beat score of die x against die y, defined as the sum over all face indices i and j in Fin n of 1 if x(i) > y(j) and 0 otherwise.
- equal_length_proportional_cake_cutting_cut_complexity_lbFor every integer n ≥ 1, if C : Fin n → Set ℝ is an equal-length proportional cake allocation among n agents under the identical valuation…
- petrial_R_log_concavity_growth_ineqFor every natural number m ≥ 4, (441 * m ^ 2 + 525 * m + 24) * 2 ^ m < 16 * 11 ^ m.
- alpha_lexical_lt_cons_samePrepending the same head to both sequences reverses the alternating lexical order on their tails.
- pgroup_coordinate_invariant_orderhom_card_modFor prime p and a p-subgroup of the coordinate-permutation group, the number of monotone maps from the n-fold product of the finite chain…
- cycle_power_fifteen_tight_type_sequence_one_alternates_core_alt00000001One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_alternates_core: under the layer-free tight-cover…
- comparison_tree_evalGiven an assignment v : Fin n → α of values in a linearly ordered type α, evaluate a comparison tree: on a leaf leaf ans, return the index…
- cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core_a0000100One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_one_iff_fourteen_core: under the layer-free tight-cover…
- cycle_power_fifteen_tight_type_sequence_six_iff_seven_core_b001One branch of the window refutation behind cycle_power_fifteen_tight_type_sequence_six_iff_seven_core: under the layer-free tight-cover…
- postage_stamp_number_neg_two_of_odd_of_mod_sixty_neExact value of the negative-allowed three-stamp number for odd h ≥ 5 with h ≢ 59 (mod 60): n_h(2) - n♭_h(2) = 1 if h ≡ 9 (mod 12), 2 if h…
- SocialChoice.FairDivision.Divisible.IsEnvyFree.isProportionalEF implies proportional for
MeasureValuationpartitions. - SocialChoice.FairDivision.Divisible.MeasureInstance.IsEnvyFreeEnvy-freeness for a measure-based divisible instance, stated in
ENNReal.
Lean source view module on GitHub
set_option autoImplicit true in set_option relaxedAutoImplicit true in /-- A total preorder: a preorder where `≤` is total (complete). This is weaker than `LinearOrder` — it does NOT require antisymmetry or decidable equality. Two distinct elements can be indifferent. This is the appropriate notion for weak preferences in utility theory and matching theory. [MSZ 2.1–2.4] -/ class TotalPreorder (A : Type*) extends Preorder A where /-- The preference relation is complete: for any `a b`, either `a ≤ b` or `b ≤ a`. -/ le_total : ∀ (a b : A), a ≤ b ∨ b ≤ a