Documentation

LeanPool.CommonNeighbourConjecture.Examples.EveryBase.AbstractSeed

Abstract data for counterexamples at every base size #

This module contains the explicit binary permutation-module seed, arbitrary base-array criterion, a quotient-independent finite tuple-colour interface with canonical quotient realizations, symbolic colour growth, and the affine exact-base-size successor bridge used by the obstruction construction.

Faithfulness and irreducibility are intentionally absent from EveryBaseSeed: they are used only later to prove primitivity and are not needed for the obstruction.

Arbitrary-length base arrays #

def SaxlCounterexamples.EveryBase.SameTupleOrbit (H : Type u_1) {V : Type u_2} [Group H] [MulAction H V] {n : } (x y : Fin nV) :

Two tuples lie in the same orbit under the diagonal action of H.

Equations
Instances For
    def SaxlCounterexamples.EveryBase.TupleRowsDistinguishing (H : Type u_1) (Q : Type u_2) {V : Type u_3} {ι : Type u_4} [Group H] [Group Q] [MulAction H V] [MulAction Q ι] {n : } (rows : ιFin nV) :

    The tuple rows distinguish every nonidentity element of the top group.

    Equations
    Instances For
      theorem SaxlCounterexamples.EveryBase.permWreath_isBaseTuple_iff (H : Type u_1) (Q : Type u_2) (ι : Type u_3) (V : Type u_4) [Group H] [Group Q] [MulAction H V] [MulAction Q ι] {n : } (rows : Fin nιV) :
      Saxl.IsBaseTuple (Saxl.PermWreath H Q ι) (ιV) rows (∀ (i : ι), Saxl.IsBaseTuple H V fun (j : Fin n) => rows j i) TupleRowsDistinguishing H Q fun (i : ι) (j : Fin n) => rows j i
      structure SaxlCounterexamples.EveryBase.TupleColourCode (H : Type u_1) (V : Type u_2) [Group H] [MulAction H V] (n : ) (C : Type u_3) :
      Type (max u_2 u_3)

      A complete finite coding of the H-orbits of base tuples.

      Instances For
        theorem SaxlCounterexamples.EveryBase.permWreath_isBaseTuple_iff_colourWord (H : Type u_1) (Q : Type u_2) (ι : Type u_3) (V : Type u_4) (C : Type u_5) [Group H] [Group Q] [MulAction H V] [MulAction Q ι] {n : } (code : TupleColourCode H V n C) (rows : Fin nιV) :
        Saxl.IsBaseTuple (Saxl.PermWreath H Q ι) (ιV) rows (∀ (i : ι), Saxl.IsBaseTuple H V fun (j : Fin n) => rows j i) Saxl.WordDistinguishing Q fun (i : ι) => code.colour fun (j : Fin n) => rows j i
        theorem SaxlCounterexamples.EveryBase.symmetricTop_isBaseTuple_iff_bijective (H : Type u_1) (V : Type u_2) (C : Type u_3) [Group H] [MulAction H V] [Finite C] {n : } (code : TupleColourCode H V n C) (rows : Fin nCV) :
        Saxl.IsBaseTuple (Saxl.PermWreath H (Equiv.Perm C) C) (CV) rows (∀ (i : C), Saxl.IsBaseTuple H V fun (j : Fin n) => rows j i) Function.Bijective fun (i : C) => code.colour fun (j : Fin n) => rows j i

        Explicit binary permutation-module seed interface #

        structure SaxlCounterexamples.EveryBase.AvoidingCycle (H : Type u_1) (Ω : Type u_2) [Group H] [MulAction H Ω] (h : H) (omega0 : Ω) :
        Type u_2

        An odd invariant cycle avoiding a distinguished point.

        Instances For
          structure SaxlCounterexamples.EveryBase.EveryBaseSeed :
          Type (max (max (u_1 + 1) (u_2 + 1)) (u_3 + 1))

          Exactly the data used by the abstract obstruction. Faithfulness and irreducibility are deliberately absent because the cycle-sum proof does not use them.

          Instances For

            Sum the binary coordinates of v over L.

            Equations
            Instances For

              Reindex an avoiding cycle by the action of its group element.

              Equations
              • One or more equations did not get rendered due to their size.
              Instances For

                Finite regular-tuple colours and orbit profiles #

                structure SaxlCounterexamples.EveryBase.VectorOrbitCode (H : Type u_1) (V : Type u_2) [Group H] [MulAction H V] (D : Type u_3) :
                Type (max u_2 u_3)

                A complete code for the vector orbits of a group action.

                • colour : VD

                  The colour assigned to a vector.

                • colour_eq_iff_sameOrbit (x y : V) : self.colour x = self.colour y ∃ (h : H), h x = y
                Instances For
                  structure SaxlCounterexamples.EveryBase.BaseArrayColours (S : EveryBaseSeed) (tail : ) :
                  Type (max (max (u_1 + 1) (u_2 + 1)) u_5)

                  A finite colour system for the tail + 1-tuples used in a generalized neighbourhood. firstColour is not extra mathematics: its compatibility field says exactly that it records the ordinary orbit of the first tuple entry. Keeping it explicit avoids quotient choice in executable files.

                  Instances For

                    Concrete finite types of all positive-length regular tuple orbits. Index t records colours of tuples of length t + 1. Positive indexing is essential: for a nontrivial group there are no regular zero-tuples, so a total colour map at length zero cannot exist.

                    • C : Type u_1

                      The colour type for each positive tuple length.

                    • fintypeC (n : ) : Fintype (self.C n)

                      Finiteness of every colour type.

                    • code (n : ) : TupleColourCode S.H S.V (n + 1) (self.C n)

                      The orbit code at each positive tuple length.

                    Instances For

                      The number of regular-tuple colours at level n.

                      Equations
                      Instances For

                        Choose a base-tuple representative of a colour.

                        Equations
                        Instances For

                          Append a vector to a representative and return the resulting colour.

                          Equations
                          Instances For
                            @[reducible, inline]

                            The permutation-wreath group associated to level n.

                            Equations
                            Instances For
                              @[reducible, inline]

                              The product module associated to level n.

                              Equations
                              Instances For

                                The canonical base rows formed from all chosen representatives.

                                Equations
                                Instances For

                                  Canonical finite quotient colours #

                                  These constructions show that the positive-length colour-tower interface is inhabited for every finite seed. Nonbase tuples receive the colour of a fixed constant regular tuple; on base tuples the colour is the actual diagonal orbit quotient.

                                  @[reducible, inline]

                                  A regular tuple of positive length n + 1.

                                  Equations
                                  Instances For

                                    Orbit equivalence on regular tuples.

                                    Equations
                                    • One or more equations did not get rendered due to their size.
                                    Instances For
                                      @[reducible, inline]

                                      The quotient colour type of regular tuples under the diagonal action.

                                      Equations
                                      Instances For
                                        @[instance_reducible]
                                        noncomputable instance SaxlCounterexamples.EveryBase.regularTupleRelDecidable (S : EveryBaseSeed) (n : ) :
                                        DecidableRel fun (x1 x2 : RegularTuple S n) => x1 x2
                                        Equations

                                        A default constant regular tuple, used to colour nonbase tuples.

                                        Equations
                                        Instances For
                                          noncomputable def SaxlCounterexamples.EveryBase.regularTupleColour (S : EveryBaseSeed) (n : ) (x : Fin (n + 1)S.V) :

                                          Colour a tuple by its orbit, using the default colour when it is not a base.

                                          Equations
                                          Instances For

                                            The canonical orbit code for regular tuples of length n + 1.

                                            Equations
                                            Instances For

                                              The canonical, genuinely inhabited positive regular-colour tower.

                                              Equations
                                              • One or more equations did not get rendered due to their size.
                                              Instances For

                                                Orbit equivalence on vectors in the seed module.

                                                Equations
                                                Instances For
                                                  @[instance_reducible]
                                                  noncomputable instance SaxlCounterexamples.EveryBase.vectorOrbitRelDecidable (S : EveryBaseSeed) :
                                                  DecidableRel fun (x1 x2 : S.V) => x1 x2
                                                  Equations

                                                  The canonical quotient code for vector orbits.

                                                  Equations
                                                  Instances For

                                                    Project a regular-tuple colour to the orbit colour of its first vector.

                                                    Equations
                                                    Instances For

                                                      Canonical finite tuple/vector orbit colours used by the profile argument.

                                                      Equations
                                                      • One or more equations did not get rendered due to their size.
                                                      Instances For

                                                        Exact tuple size and the affine successor bridge #

                                                        A technically convenient strengthening of Saxl.ExactBaseSize: smaller ordered tuples are excluded even before imposing injectivity.

                                                        Equations
                                                        Instances For
                                                          theorem SaxlCounterexamples.EveryBase.isBaseTuple_injective_of_no_predecessor {G : Type u_1} {X : Type u_2} [Group G] [MulAction G X] {n : } (x : Fin (n + 1)X) (hbase : Saxl.IsBaseTuple G X x) (hprev : ¬∃ (y : Fin nX), Saxl.IsBaseTuple G X y) :