Questions tagged [finite-geometry]
Galois geometry, finite projective and affine spaces, polar spaces, partial geometries, generalized polygons, near polygons, and other finite incidence geometries.
65 questions
1
vote
1
answer
65
views
Dual of blocking sets in finite geometry
Let $V$ be an $n$-dimensional vector space over the finite field of cardinality $q$ and let $W_1,\ldots,W_m$ be hyperplanes of $V$ such that
$$V=\bigcup_{i=1}^mW_i \,\,\hbox{ and }\,\,0=\bigcap_{i=...
- 223
4
votes
1
answer
385
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 ...
- 935
5
votes
2
answers
139
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 ...
- 131
41
votes
2
answers
5k
views
Projective Plane of Order 12
I asked this question on the new Theoretical Computer Science "overflow" site, and commenters suggested I ask it here. That question is here, and it contains additional links, which I doubt I can ...
- 35.5k
5
votes
1
answer
341
views
Which finite projective planes can have a symmetric incidence matrix?
As the title says. Which finite projective planes admit a symmetric incidence matrix?
I am not an expert in the field at all, but I consulted with one. He claimed that $PG(2, \mathbb F_q)$ can always ...
- 6,614
4
votes
0
answers
143
views
Non-Desarguesian finite projective planes with ≤3 (non-collinear) chosen points, and coordinatisation
It is well-known that an arbitrary projective plane can have very different symmetry group to a field plane. In particular, the symmetries are not transitive on the set of fundamental quadrangles. ...
- 14.6k
13
votes
1
answer
345
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 ...
- 82.7k
10
votes
1
answer
516
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....
- 114
9
votes
2
answers
505
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 ...
- 9,501
7
votes
0
answers
301
views
Arrangement of subspaces over finite fields
I'm trying to find out what is already known about the following setup.
Let $V$ be an $n$-dimensional vector space over a finite field $F_q$ (I'm mostly interested in the case where $q$ is prime), and ...
- 1,197
11
votes
1
answer
269
views
Does every $C_4$-free bipartite graph lies in some finite projective plane?
A projective plane $Π$ is a 3-tuple $(P,L,I)$ where $P$ and $L$ are sets, and $I$ is a relation between $P$ and $L$, such that:
For every two elements $p_1$, $p_2\in P$, there exists a unique ...
- 85.6k
16
votes
1
answer
395
views
Geometric interpretation of the exceptional isomorphism $PSp(4,3)=PSU(4,2^2)$
It is well-known that there is an isomorphism between $PSp(4,3)$ (the symplectic group of dimension $4$ over $\mathbb F_3$) and $PSU(4,2^2)$ (the unitary group defined by $4\times4$ unitary matrices ...
- 11.2k
3
votes
0
answers
127
views
$\left< 15\right>^7/15$-womcode construction
In the article Womcodes constructed with projective geometries Frans Merkx constructed several good wom-codes (write-once memory codes, see How to reuse a "write-once" memory by Rivest & Shamir ...
- 12.3k
2
votes
0
answers
35
views
Different powers of a primitive root simultaneously lying in a subspace
Let $p$ be a large prime and let $\alpha$ be a root of a primitive quadratic polynomial over $\mathbb{F}_p$. Let $N$ be an integer parameter of size proportional to $p$ and $$V = \{\alpha + b : b \in \...
- 2,283
4
votes
1
answer
186
views
Is there a unique Baer subplane in a finite Desarguesian projective plane?
An order-$m$ subplane of a finite projective plane of order $n$ is called a Baer subplane if $n=m^2$.
It is known that the projective plane $PG(2,q)$ is a Baer subplane of the Desarguesian ...
- 9,501
4
votes
0
answers
250
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 ...
- 23k
6
votes
1
answer
297
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 ...
- 61.9k
4
votes
0
answers
192
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 ...
- 23k
2
votes
0
answers
59
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 ...
- 1,389
9
votes
1
answer
399
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 graphs ...
CommunityBot
- 1
5
votes
0
answers
119
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 finite ...
CommunityBot
- 1
2
votes
0
answers
86
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 ...
- 23k
6
votes
1
answer
444
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 ...
- 9,720
3
votes
1
answer
164
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)\...
- 30.1k
10
votes
1
answer
561
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|&...
- 1,384
2
votes
1
answer
302
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&...
- 1,300
9
votes
0
answers
245
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 ...
- 23k
16
votes
1
answer
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}/...
- 30.1k
6
votes
1
answer
458
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$ ...
- 223
5
votes
0
answers
89
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(...
- 23k
7
votes
1
answer
294
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?
- 366
3
votes
0
answers
100
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 ...
- 12.3k
1
vote
1
answer
773
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 \...
- 149k
5
votes
1
answer
355
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 ...
- 11.2k
11
votes
1
answer
298
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 ...
- 16.6k
7
votes
1
answer
330
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 ...
CommunityBot
- 1
15
votes
1
answer
417
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 ...
- 9,720
5
votes
1
answer
557
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}$...
- 171
5
votes
1
answer
343
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 ...
- 43.7k
5
votes
1
answer
140
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 ...
- 24.8k
4
votes
3
answers
781
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 ...
CommunityBot
- 1
13
votes
2
answers
1k
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 ...
CommunityBot
- 1
6
votes
1
answer
303
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 ...
CommunityBot
- 1
4
votes
1
answer
271
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^...
- 7,249
1
vote
1
answer
145
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 ...
CommunityBot
- 1
3
votes
3
answers
611
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 ...
- 101
5
votes
1
answer
460
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.
...
CommunityBot
- 1
11
votes
2
answers
792
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,...
- 1,197
14
votes
0
answers
552
views
Who conjectured that a transitive projective plane is Desarguesian?
The only known finite projective plane with a transitive automorphism group is the Desarguesian plane $PG(2,q)$ and it seems likely that there are no others, although this is not (quite) proved.
...
- 1,197
39
votes
2
answers
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} $ ...
- 1,197