Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [finite-geometry]

Galois geometry, finite projective and affine spaces, polar spaces, partial geometries, generalized polygons, near polygons, and other finite incidence geometries.

5
votes
1answer
123 views

Moore Graphs and Finite Projective Geometry

In a comment on a blog post from 2009 about the hypothetical Moore graph(s) of degree 57 and girth 5, Gordon Royle offered the following observation (reproduced here in full for the sake of ...
4
votes
0answers
150 views

Birkhoff – von Neumann for “$k$-stochastic matrices”

Recall that a doubly-stochastic matrix is a square matrix with non-negative elements such the sum of the elements in every row, as well as in every column, is $1$. The set of doubly-stochastic ...
6
votes
1answer
210 views

Covering the finite plane with lines

This is, essentially, a geometrically rendered version of the question I asked a week ago, with the emphases slightly shifted; it seems more natural and appealing (to me, at least) in this form. Let ...
4
votes
0answers
179 views

Forcing scalar products to avoid prescribed values

Let $p$ be a prime, and $n\ge 1$ an integer number. Suppose that the (not necessarily distinct) vectors $v_1,\dotsc,v_N \in{\mathbb F}_p^n$ satisfy the following condition: \begin{gather} \text{For ...
2
votes
0answers
39 views

Is the finite projective plane stable as an extremal set system?

Let $\Sigma$ be a set of $|\Sigma| = n$ subsets of the universe $[n]$, each of size $k$, with the property that any two of these subsets intersect on at most one element. It is easy to see that the ...
5
votes
0answers
69 views

What (if anything) is the connection between the Feit-Higman Theorem and the regular plane tilings?

Here are two facts that are superficially similar. Tiling Theorem: The only regular tilings of $\mathbb{R}^2$ are achieved by triangles, squares, and hexagons. Feit-Higman Theorem: The only ...
2
votes
0answers
74 views

A system of homogeneous linear equations

This is the "real-life" (but slightly more technical) version of a question I have asked recently. For a prime $p>10$, let $\mathcal L_X$, $\mathcal L_Y$, and $\mathcal L_Z$ denote the pencils of ...
4
votes
1answer
159 views

Kantor's Singer cycle theorem

I'm trying to understand the proof of Kantor's Singer cycle theorem, which asserts that if $G$ is a subgroup of $\operatorname{GL}(n,q)$ containing a Singer cycle then $\operatorname{GL}(n/s,q^s) \leq ...
3
votes
1answer
133 views

A system of linear equations related to the geometry of a finite plane

Let $\mathcal L$ denote the set of all lines in $\mathbb F_p^2$ parallel to one of the lines $$ X:=\{(x,0)\colon x\in\mathbb F_p \}, \ Y:=\{(0,y)\colon y\in\mathbb F_p \}, \ Z:=\{(z,z)\...
9
votes
1answer
302 views

Are bipartite Moore graphs Hamiltonian?

This is motivated by a computer-generated conjecture that bipartite distance-regular graphs are hamiltonian. I decided to check the case of Moore graphs first. The cycles and complete bipartite ...
8
votes
1answer
375 views

How many rich directions does a set in $\mathbb F_p^2$ determine?

$\newcommand{\F}{\mathbb F}$ A subset $P$ of the affine plane $\F_p^2$ is said to determine a direction if there is a line in this direction containing at least two points of $P$. A set of size $|P|&...
2
votes
1answer
104 views

For which finite projective planes can the incidence structure be written as a circulant matrix?

It is well known that the projective plane of order $2$ can be represented by the circulant matrix $M_2:=circ(x,x,1,x,1,1,1)= \begin{pmatrix} x&x&1&x&1&1&1\\ 1&x&x&...
8
votes
0answers
183 views

Almost blocking sets in $\mathbb F_q^2$

$\newcommand{\F}{{\mathbb F}}$ Let $q$ be an odd prime power. A blocking set in the affine plane $\F_q^2$ is a set blocking (meeting) every line. A union of two non-parallel lines is a blocking set ...
16
votes
1answer
3k views

How do I see the equality $57 = 3 \times 19$ geometrically?

Consider the finite field ${\bf F}_p$ and its cubic extension ${\bf F}_{p^3}$. The multiplicative group ${\bf G}_m({\bf F}_{p^3})$ contains the multiplicative group ${\bf G}_m({\bf F}_p) \cong {\bf Z}/...
5
votes
0answers
80 views

Lines meeting a given set in a unique point

Let $p$ be a fixed prime, and suppose that $S$ is a subset of the affine plane $\mathbb F_p^2$. If $|S|\le p+1$, then by the pigeonhole principle, through any given point $s\in S$ there is a line $L=L(...
5
votes
1answer
173 views

Largest number of points one can pick in finite projective space without getting three on a line

Consider the projectivization $\mathbb P\mathbb F_p^n$ of $\mathbb F_p^n$. How large a set $B \subseteq \mathbb P \mathbb F_p^n$ can I pick so that no three points of $B$ lie on the same line?
3
votes
0answers
78 views

Applications of finite Bolyai-Lobachevsky planes

Google scholar gives more than 200 articles comcerning finite Bolyai-Lobachevsky (BL) planes. Usually they devoted to construction of such objects (axioms may be different). Are their any ...
1
vote
1answer
200 views

Elliptic Curve, characteristic equation of Frobenius endomorphism relation to isogeny

Let E be an elliptic curve over $F_p$. Suppose that its j invarient is not supersingular and that $j\neq 0 $ or 1728. Then the modular polynomial $\Phi_l(j,T)$ has a zero $\tilde{\jmath} \in \...
4
votes
1answer
118 views

Generalization of finite-projective-plane with more than one intersection point

In a finite projective plane, each two points appear together in exactly one line, and each two lines intersect in exactly one point. It is known that, if each line contains $n+1$ points, then the ...
13
votes
1answer
157 views

Status of the basis exchange condition for symplectic matroids

Let $J_n := \{1,2,3,\ldots,n,1^*,2^*,\ldots,n^*\}$ with the involution $x\mapsto x^*$ exchanging $i$ and $i^*$ for $1\leq i\leq n$. The following is supposed to be standard, but to avoid any doubt as ...
11
votes
1answer
253 views

Is there a well-known notion of orientability for finite geometries?

I'm wondering if the notion of an orientable/non-orientable manifold has any reasonable extension that allows for a similar classification of finite geometries. For example, the real projective plane ...
6
votes
1answer
207 views

Large gaps in Singer's difference sets

This question is related to the question I asked earlier. For a natural number $n$, a set $D$ of integer numbers is called a $n$-cyclic difference set if each integer number $x\notin n\mathbb Z$ can ...
14
votes
1answer
321 views

What is the smallest cardinality of a self-linked set in a finite cyclic group?

A subset $A$ of a group $G$ is defined to be self-linked if $A\cap gA\ne\emptyset$ for all $g\in G$. This happens if and only if $AA^{-1}=G$. For a finite group $G$ denote by $sl(G)$ the smallest ...
4
votes
1answer
201 views

Which cyclic groups admit a difference set?

Problem 1. For which $n$ does the cyclic group $C_n$ admit a difference set $D\subset C_n$, i.e., a set such that each non-unit element $x\in C_n$ can be uniquely written as the difference $x=ab^{-1}$...
3
votes
1answer
218 views

Large gaps in Singer planar difference sets?

By a classical result of Singer (1938), for a prime number $p$ the cyclic group $C_n$ of order $n=1+p+p^2$ contains a subset $D$ of cardinality $|D|=1+p$ such that $DD^{-1}=C_n$. Such set $D$ is ...
5
votes
1answer
95 views

Is there literature on finite geometries with ordered lines?

A difference between finite geometries and (e.g.) Euclidean space is that "lines" in finite geometries are unordered subsets of the universe, while "lines" in Euclidean space are ordered subsets of ...
4
votes
3answers
314 views

Does there exist a finite hyperbolic geometry in which every line contains at least 3 points, but not every line contains the same number of points?

It seems to me that the answer should be yes, but my naive attempts to come up with an example have failed. Just to clarify, by finite hyperbolic geometry I mean a finite set of points and lines such ...
12
votes
2answers
671 views

The exceptional isomorphism between PGL(3,2) and PSL(2,7): geometric origin?

It is well-known there is an isomorphism between $GL(3,2)=PGL(3,2)$, the automorphism group of the Fano plane (i.e. the projective plane over the finite field with two elements), and $PSL(2,7)$, which ...
6
votes
1answer
181 views

Maximum number of elements in union of subspaces

Let $V$ be a $m$-dimensional vector space over $\mathbb{F}_q$ and $1<\ell<m-1$. Let $r$ be a positive integer such that $r\ell\leq m$. QUESTION. What is the maximum number of elements in the ...
4
votes
1answer
245 views

Square-free sets in $\mathbb F_2^n\oplus\mathbb F_2^n$

A square in $\mathbb F_2^n\oplus\mathbb F_2^n$ is a quadruple of the form $$ (u,v)+\{(0,0),(0,d),(d,0),(d,d)\},\quad u,v,d\in\mathbb F_2^n,\ d\ne 0. $$ A set $A\subset\mathbb F_2^n\oplus\mathbb F_2^...
3
votes
1answer
82 views

Sets blocking every $2$-flat in $AG(n,2)$

The following may be well-known $-$ but not known to me: What is the smallest possible size of a set in ${\mathbb F}_2^n$ that blocks every $2$-flat? Here "blocks" means "have a non-empty ...
1
vote
1answer
91 views

Finding a set of disjoint affine subspaces such that their union is equal to a given subset of $\mathbb{F}_2^n$

Suppose I'm given a set of point $S = \{x_1, \dots, x_m \} \subseteq \mathbb{F}_2^n$, and the following task. Find a set of disjoint affine subspaces of $\mathbb{F}_2^n$, $A_1, \dots, A_k$ satisfying ...
10
votes
2answers
492 views

Blocking sets in three dimensional finite affine spaces

What is the smallest possible size of a set of points in $\mathbb{F}_q^3$ which intersects (blocks) every line? Clearly the union of three affine hyperplanes that intersect in a singleton, say $x = 0,...
5
votes
1answer
293 views

$(n-2)$-blocking sets in $AG(n,2)$

Let's define $k$-blocking set in affine space $AG(n,q)$ a set that meets every coset (translate of subspace) of dimension $k$. I have seen a lot work related to minimal $(n-1)$-blockings set. ...
3
votes
1answer
202 views

An upper bound on the number of sets of parallel lines covering points in a finite plane?

Let $\mathbb{F}$ be a finite field of characteristic $2$. Let $L_m$ denote the set of lines in $\mathbb{F}^2$ with slope $m\in\mathbb{F}$, that is, all parallel lines of the form $y=mx+b$. Consider a ...
7
votes
0answers
134 views

The Maximum Number of Lines Contained in the Point Set of a Finite Projective Plane

Consider a finite projective plane of order $q$. Define $f(m)$ to be the maximum number of lines completely contained in any point set of size $m$, where $1 \leq m \leq q^2+q+1$. I would like to ...
6
votes
1answer
313 views

Applications of small Kakeya sets over finite fields

It was proved by Dvir that a Kakeya set in $\mathbb{F}_q^n$ has size at least $q^n/n!$, a bound which was later improved to $q^n/2^n$. For $n = 2$ and $q$ odd the exact bound is $q(q+1)/2 + (q-1)/2$ ...
4
votes
0answers
203 views

Sets of spreads in graphs

Let $G$ be a graph. A $k$-spread is a set of cliques of order $k$ which partition the vertex set (so $k|n$, where $n$ is the number of vertices). A partial $k$-resolution of $G$ is a set of pairwise ...
37
votes
2answers
1k views

How close can one get to the missing finite projective planes?

This question can be interpreted as an instance of the Zarankiewicz problem. Suppose we have an $n\times n$ matrix with entries in $\{0,1\}$ with no $\begin{pmatrix}1 & 1\\ 1& 1\end{pmatrix} $ ...
2
votes
1answer
167 views

Is inner product preserved only by the stabiliser in a finite reflection group?

Is the following statement true for finite reflection groups? Let $G$ be a finite reflection group acting on $\mathbb{R}^n$, let $x, y\in \mathbb{R}^n$ and let $z$ be in the orbit of $y$. If $\...
10
votes
2answers
404 views

Is there a hyperplane avoiding two independent sets?

Let $V$ be a vector space over a field with $5$ elements, $A,B \subseteq V$ independent subsets. Must there be a subspace of $V$ of codimension 1 disjoint from $A \cup B$?
7
votes
0answers
276 views

Subplanes of Finite Projective Planes

If a finite projective plane $\pi_1$ of order $m$ contains, as a sub plane, a finite projective plane $\pi_2$ of order $n$, then $m \geq n^2$ with equality holding only in the case of a Baer sub plane....
4
votes
2answers
346 views

Finding the set of all $0$-$1$ vectors in an affine subspace

We are given a $0$-$1$ matrix $A$ with constant row and column sum, and we need to find out if there exists a $0$-$1$ vector in the solution space of $Ax = \mathbf{1}$ over $\mathbb{Q}$ (or $\mathbb{Z}...
2
votes
0answers
316 views

Enumerating certain types of permutation polynomials

Given a prime power $q$, I would like to enumerate (preferably up to isomorphism*) all the permutation polynomials $f(x)$ on $K = GF(q^3)$ satisfying the following conditions: $f(ax) = af(x)$ for all ...
5
votes
0answers
168 views

A question on hyperplanes in partial linear spaces and hypergraphs

A partial linear space (or a linear hypergraph) is a point line geometry $(P,L,I)$ where for every pair of points there is at most one line incident with both of them. A hyperplane in a partial linear ...
4
votes
1answer
219 views

Point-Hyperplane incidence in finite projective spaces

Let $P$ be a finite projective space of order $q$ and dimension $d$. I am interested in finding the least $k$ such that for any set $S$ of $k$ points of $P$, and for any set $S'$ of $k$ hyperplanes of ...
3
votes
0answers
122 views

Intersection of two trace equations over finite fields

Let $F_q$ be a finite field with $q$ elements. Let $n$ be an integer and $Tr:F_{q^n} \rightarrow F_q$ the trace function. My question is: For which integer $k$, $$\{x: Tr(x)=0\}\cap\{x: Tr(x^k)=0\}=\{...
3
votes
3answers
382 views

On MDS code property

Is there a code that is Maximum Distance Separable and not isomorphic to Reed Solomon Codes? When is a MDS code isomorphic to Reed Solomon Code? Is there an easy test? If so, could someone provide ...
2
votes
0answers
243 views

A problem in Galois Geometry

Given a prime $p$, out of $N$ vectors of length $p^k$ over $\Bbb F_2$ of Hamming weight $w^{k}$ that are chosen, how many vectors can there be with pairwise Hamming distance at least $2w^{k}$ given ...
12
votes
2answers
609 views

Who constructed the projective plane of order $4$ from $K_6$?

I have been trying to hunt down the original reference for the construction of the projective plane of order $4$ from the complete graph on $6$ vertices. The reference I have at hand are Cameron and ...