Skip to content

Error in Flag Transitivity #57

Description

@CAPiedade

Dear developers of FinInG

I must disclose that I have encountered an error in the implementation of checking flag-transitivity of a coset geometry / coset incidence system.
By checking the code, I can see this derives from the fact that the implementation relies on a result in the Handbook of Incidence Geometry, which itself relies on a result of Buekenhout and Hermand that, in its generality, states:

Let P(I) be the set of all the subsets of I and let \alpha: P(I)\setminus{Ø} → I be a function such that \alpha(J) \in J for every J \subset I, with J \neq Ø. Then G is flag-transitive on coset geometry \Gamma(G; (G_i)_{i \in I}) if and only if, for every J\subset I such that |J| ≥ 3, we have \cap_{j\in J - \alpha(J)} (G_j G_{\alpha(J)}) = (\cap_{j\in J - \alpha(J)} G_j) G_{\alpha(J)}.

The example found in the Handbook of Incidence Geometry takes the minimum of J as the \alpha(J).
However, unfortunately, some choices of functions might fail to evaluate whether a coset incidence system is flag-transitive or not.

For example, take as generators

gap> r0 := (1,2)(3,5)(4,6)(7,8);
gap> r1 := (1,2)(3,7)(4,5)(6,8);
gap> r2 := (1,3)(2,5)(4,7)(6,8);
gap> r3 := (1,4)(2,6)(3,7)(5,8);

and as maximal parabolic subgroups

gap> G0 := Subgroup(G,[r1,r2,r3]);
gap> G1 := Subgroup(G,[r0,r2,r3]);
gap> G2 := Subgroup(G,[r0,r1,r3]);
gap> G3 := Subgroup(G,[r0,r1,r2]);

The coset incidence system, with the current implementation, will give that the it is flag-transitive.

gap> CG := CosetGeometry(G,[G0,G1,G2,G3]);
gap> IsFlagTransitiveGeometry(CG);
true

However, one can check that (G0 \cap G2) G3 \neq (G0 G3) \cap (G2 G3)
Indeed, the size of (G0 \cap G2) G3 is 72 while (G0 G3) \cap (G2 G3) has size 96.

Using hence the result of Buekenhout and Hermand would require unfortunately testing all possible functions \alpha, which doesn't seem feasible.
After also discussing with some colleagues, we believe that the implementation might check flag-transitivity if the coset incidence system is proven to be a geometry (which, following the manual, is checked by checking the flag-transitivity).

Since I have published work (including an Atlas of flag-transitive structures) depending on using this function, it would be important for me if this would be corrected so that I could re-test again all my previous work.

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions