# Tag Info

13

I believe that a finite geometric proof is given by Jean Dieudonné here: Dieudonné, Jean, Les isomorphismes exceptionnels entre les groupes classiques finis, Can. J. Math. 6, 305-315 (1954). ZBL0055.01904. If you go to Section 7 of the given paper you will see the proof. Dieudonné displays the required isomorphism using a 1-1 correspondence between the 40 ...

12

This is an open problem posed by Erdos in "Some old and new problems in various branches of combinatorics" (see section 6). There hasn't been any substantial progress since then. After posing the question Erdos writes "I have no idea how to attack this problem", and that seems to be state of the art.

10

There is an explanation of sorts in Section 1.4 of Elkies's "The Klein quartic in number theory". There is a three-dimensional lattice $L$ over the cyclotomic field $k=\mathbf Q(\zeta_7)$, and $G$ can be defined as its group of isometries. The resulting three-dimensional representation of $G$ has the unusual property of remaining irreducible when reduced ...

10

The difference cover problem has been better studied in the context of $\mathbf{Z}$. Redei, Renyi, and others in the 40s asked for the size of the smallest set $A$ such that $A-A$ covers $\{1,2,\dots,N\}$. They proved an upper bound of roughly $\sqrt{8/3} \sqrt{N}$. To prove this they combined Singer's construction of a perfect difference set with the "...

10

The term for such sets is "caps". The problem you ask was posed by Bose ("Mathematical theory of the symmetrical factorial design", Sankhyā 8 (1947) 107–166), and is important in relation to coding theory: see Hill, A first course in coding theory (1986), around figure 14.9. At least at the time of Hill's book from which the following values are taken, the ...

9

No you cannot have very big gaps in a perfect difference sets -- the elements in a perfect difference set will be pretty uniform. Suppose $A$ is a perfect difference set $\mod n$ with $n=1+p+p^2$ as above. Put $${\hat A}(k) = \sum_{a \in A} e(ak/n).$$ Since $A$ is a perfect difference set, for any $k\neq 0$ one has $$|{\hat A}(k)|^2 = |A| + \sum_{a ... 8 What you called difference sets in cyclic groups are usually called PLANAR cyclic difference sets, namely those with \lambda equal to 1. The question you asked here has been studied for many years. Singer's construction from 1938 shows that for any prime power n, there is a planar cyclic difference set of order n. In the other direction, probably the ... 8 To do that you would need a notion of a non-orientable and an orientable linear transformation, i.e., essentially a notion of a "positive" and "negative" determinant, where "positive" determinants would form a subgroup not containing the element -1. This works for the field \mathbb{Z}/p\mathbb{Z} if and only if the prime p satisfies p\equiv 3 (mod\; ... 8 Adding to the allure of this deadly siren song is the fact that there are constructions of this sort for the Moore graph of degree 3 (the Petersen Graph with 10 vertices and independence number 4) and the Moore Graph of degree 7 ( the Hoffman-Singleton graph with 50 points and independence number 15.) The only other possible degrees are 2 (a ... 7 V. Dotsenko's construction, on math.stackexchange: https://math.stackexchange.com/questions/1401/why-psl-3-mathbb-f-2-cong-psl-2-mathbb-f-7/1450#1450 may fit your requirement "combinatorial mapping of these geometries that induces an isomorphism". 6 Here is a slightly better lower bound. If there are fewer than 2q^2 points then there is some line that hits the set at most once. Consider the q+1 planes containing a line containing one point. There must be at least 2q-2 other points in each of those planes to meet all lines in the plane, for a total of 1+(q+1)(2q-2) = 2q^2-1 points. So, 2q^2-1 \... 5 Pick naturals q,m,l,r. Assume q is a prime power and 2l\leq m. If r\leq q^l+1 then the maximal size of the union of r many (m-l)-dimensional sub-vector spaces of V=\mathbb{F}_q^m is S=rq^{m-l}-(r-1)q^{m-2l}. If r\geq q^l+1 then the size is q^m. Note that for r=q^l+1 we get S=q^m. Since the maximal size of the union is obviously ... 5 Not much is known for the general case. Let m(k, n, q) denote the minimum size of an k-blocking set in AG(n, q). Trivially we have m(0, n, q) = q^n and m(n, n, q) = 1. By Jamison/Brouwer-Schrijver we get m(n-1, n, q) = 1 + n(q-1) as you have mentioned. To at least give bounds on other values we can prove the following inequality$$qm(k, n-1, q) ...

5

Yes, this has been studied and is indeed known as ordered geometry or the study of betweenness spaces: https://en.m.wikipedia.org/wiki/Ordered_geometry

5

I recall being told (by Neil White I think, but he might have been reporting an observation of Borovik) that the Gelfand–Serganova exchange condition is wrong. Unfortunately I no longer recall the counterexample, and I agree with you that this is an unfortunate lacuna in the literature. I would suggest contacting Borovik. Of course if you can straighten ...

4

Take a 2-$(v,4,1)$ design on $v$ points and delete one block, along with the four points on it. In the original system each point is on exactly $(v-1)/3$ blocks, so if we assume $v\ge25$ the geometry we get by deleting one block is hyperbolic, all blocks have at least three points, and there are blocks of size three and size four.

4

I became interested in Kakeya sets because they have the interesting property that a Kakeya set in a projective plane cannot be a subset of a blocking set, and with the exception of the full plane with two lines removed, Kakeya sets are the only sets with this property. As far as state of the art in higher dimensions, not much seems known. The article http:/...

4

I guess you exclude trivial MDS codes, generalized Reed-Solomon codes, and MDS codes that can be obtained by code extension. If you exclude them all, there are still a bunch of MDS codes. In general, MDS codes of length $n$ and dimension $k$ over $\mathbb{F}_q$ are equivalent to $n$-arcs in $\text{PG}(k-1,q)$. Generalized Reed-Solomon codes are $n$-arcs ...

4

Even though it is NP-complete, you can do a lot better than searching through all $2^n$ possibilities. In practice, you might try a SAT solver, with the clauses $\bigvee_{j: A_{ij} = 1} x_j$ for each row $i$ and $\overline{x_j} \vee \overline{x_k}$ for each pair $(j,k)$ such that for some row $i$, $A_{ij} = 1$ and $A_{ik} = 1$. This can sometimes solve a ...

4

Let me adjust notation slightly -- the $k$ in the original post is more usually a $\lambda$ in the literature. Thus the concept you want is this: Definition. A symmetric $2-(v,k,\lambda)$ design is a pair $(\Omega, \mathcal{B})$ where $\Omega$ is a set of size $v$ and $\mathcal{B}$ is a set of $k$-subsets of $\Omega$ such that: any 2 points of $\... 4 To answer your questions: 1) A projective plane admits a circulant incidence matrix if and only if the automorphism group contains a cyclic group acting regularly on points and regularly on blocks. Equivalently, the projective plane comes from a difference set. The automorphism group of the projective plane coming from the Dickson near-field of order 9 is ... 4 Let$C>0$be any fixed number. Take$p-3$horizontal lines and$p-b$vertical lines where$p\gg b\gg C$. If we want to stay within$2p+C-3$lines, we should be able to cover some$3\times b$rectangular configuration by at most$b+C$lines of any prescribed slopes$a_1,\dots, a_{b+C}\ne 0$. Notice that we have$3b$points to cover and each line can cover ... 3$q^{\frac{d}{2}}$is a lower bound. Assume$d=2e$, a$d$-dimensional projective space has$d+1=2e+1$variables$x_0,x_1,\dots,x_e,x_{e+1},\dots,x_{2e}$. Let the points be all vectors with$x_0$coordinate$1$,$x_1$through$x_e$arbitrary, and$x_{e+1}$through$x_{2e}$zero. Similarly, let the hyperplanes be vectors with$x_0$coordinate$1$,$x_1$through ... 3 It has been proved by Simeon Ball that for$k \leq p$, all$[n, k, n-k+1]_q$codes are Reed-Solomon codes, where$q = p^h$. See Corollary 9.2 in the following paper: Ball, S. On sets of vectors of a finite vector space in which every subset of basis size is a basis. J. Eur. Math. Soc. 14: pp. 733-748 (2012). http://www.ems-ph.org/journals/show_abstract.php?... 3 If a set$S$is evenly covered by lines in$n$slopes, then$n \le |S|-1$because through every point$p$, there are at most$|S|-1$lines connecting$p$to other points in the set, and any other slope of line would include a line intersecting$S$in just$p$. Here are some examples achieving that bound: Hyperovals in subfields. A hyperoval in the ... 3 Let$d_n$be the maximal density of a squarefree set in$\mathbb F_2^n\oplus\mathbb F_2^n$. Then it is unknown whether there exists a constant$c < 1$such that$d_n = O(c^n)$. Indeed, such a result would imply a similar bound for cornerfree sets, and the best known bound for cornerfree sets is (to my knowledge) that one, which gives a density$= O \left( ...

3

An $N$-element set contains no 2-flat iff all pairwise sums of its elements are distinct, so ${N\choose 2}\leq 2^n$, whence $N<1+2^{(n+1)/2}$. [UPDATE] It seems that I have a construction providing $2^n$ points in $\mathbb F_2^{2n}$, confirming that $c=\sqrt2$ is optimal. The idea is as follows. Denote $U=\mathbb F_2^n$. Assume that we have a map $\phi\... 3 Firstly, in my previous answer I showed that the gaps are bounded by$O(n^{\frac 34} \log n)$(and one can remove the$\log$with a little more care). I expect that this is the best known bound on the gap. Problem 2 is definitely an open problem. Suppose one can show that there is a gap of size$C\sqrt{n}$. By translating the perfect difference set, ... 3 Here is an improvement of the upper bound which I found in The polynomial method in Galois geometries'' by Simeon Ball. See page number 4. The known constructions are somewhat crude. For example, let$S$be a set of points of$AG(3,q)$with the property that every line is incident with a point of$S$. For$q\$ square, the smallest known example ...

Only top voted, non community-wiki answers of a minimum length are eligible