BZPEER

preprint2022arXiv

Orbits of the class $\mathcal{O}_6$ of lines external with respect to the twisted cubic in $\mathrm{PG}(3,q)$

In the projective space $\mathrm{PG}(3,q)$ , we consider orbits of lines under the stabilizer group of the twisted cubic. In the literature, lines of $\mathrm{PG}(3,q)$ are partitioned into classes, each of which is a union of line orbits. We propose an approach to obtain orbits of the class named $\mathcal{O}_6$ , whose complete classification is an open problem. For all even and odd $q$ we describe a family of orbits of $\mathcal{O}_6$ and their stabilizer groups. The orbits of this family include an essential part of all $\mathcal{O}_6$ orbits.

preprint2021arXiv

On cosets weight distributions of the doubly-extended Reed-Solomon codes of codimension 4

We consider the $[q+1,q-3,5]_q3$ generalized doubly-extended Reed-Solomon code of codimension $4$ as the code associated with the twisted cubic in the projective space $\mathrm{PG}(3,q)$ . Basing on the point-plane incidence matrix of $\mathrm{PG}(3,q)$ , we obtain the number of weight 3 vectors in all the cosets of the considered code. This allows us to classify the cosets by their weight distributions and to obtain these distributions. The weight of a coset is the smallest Hamming weight of any vector in the coset. For the cosets of equal weight having distinct weight distributions, we prove that the difference between the $w$ -th components, $3<w\le q+1$ , of the distributions is uniquely determined by the difference between the $3$ -rd components. This implies an interesting (and in some sense unexpected) symmetry of the obtained distributions.

preprint2021arXiv

Twisted cubic and orbits of lines in $\mathrm{PG}(3,q)$ , II

In the projective space $\mathrm{PG}(3,q)$ , we consider the orbits of lines under the stabilizer group of the twisted cubic. In the literature, lines of $\mathrm{PG}(3,q)$ are partitioned into classes, each of which is a union of line orbits. In this paper, all classes of lines consisting of a unique orbit are found. For the remaining line types, with one exception, it is proved that they consist exactly of two or three orbits; sizes and structures of these orbits are determined. Also, the subgroups of the stabilizer group of the twisted cubic fixing lines of the orbits are obtained. Problems which remain open for one type of lines are formulated and, for $5\le q\le37$ and $q=64$ , a solution is provided.

preprint2020arXiv

On integral weight spectra of the MDS codes cosets of weight 1, 2, and 3

The weight of a coset of a code is the smallest Hamming weight of any vector in the coset. For a linear code of length $n$ , we call integral weight spectrum the overall numbers of weight $w$ vectors, $0\le w\le n$ , in all the cosets of a fixed weight. For maximum distance separable (MDS) codes, we obtained new convenient formulas of integral weight spectra of cosets of weight 1 and 2. Also, we give the spectra for the weight 3 cosets of MDS codes with minimum distance $5$ and covering radius $3$ .

preprint2020arXiv

On planes through points off the twisted cubic in $\mathrm{PG}(3,q)$ and multiple covering codes

Let $\mathrm{PG}(3,q)$ be the projective space of dimension three over the finite field with $q$ elements. Consider a twisted cubic in $\mathrm{PG}(3,q)$ . The structure of the point-plane incidence matrix in $\mathrm{PG}(3,q)$ with respect to the orbits of points and planes under the action of the stabilizer group of the twisted cubic is described. This information is used to view generalized doubly-extended Reed-Solomon codes of codimension four as asymptotically optimal multiple covering codes.

preprint2020arXiv

Tables, bounds and graphics of short linear codes with covering radius 3 and codimension 4 and 5

The length function $\ell_q(r,R)$ is the smallest length of a $q$ -ary linear code of codimension (redundancy) $r$ and covering radius $R$ . The $d$ -length function $\ell_q(r,R,d)$ is the smallest length of a $q$ -ary linear code with codimension $r$ , covering radius $R$ , and minimum distance $d$ . By computer search in wide regions of $q$ , we obtained following short codes of covering radius $R=3$ : $[n,n-4,5]_q3$ quasi-perfect MDS codes, $[n,n-5,5]_q3$ quasi-perfect Almost MDS codes, and $[n,n-5,3]_q3$ codes. In computer search, we use the step-by-step leximatrix and inverse leximatrix algorithms to obtain parity check matrices of codes. The new codes imply the following new upper bounds (called lexi-bounds) on the length and $d$ -length functions: $\ell_q(4,3)\le\ell_q(4,3,5)<2.8\sqrt[3]{\ln q}\cdot q^{(4-3)/3}=2.8\sqrt[3]{\ln q}\cdot\sqrt[3]{q}=2.8\sqrt[3]{q\ln q}~\text{for}~11\le q\le7057;$ $\ell_q(5,3)\le\ell_q(5,3,5)<3\sqrt[3]{\ln q}\cdot q^{(5-3)/3}=3\sqrt[3]{\ln q}\cdot\sqrt[3]{q^2}=3\sqrt[3]{q^2\ln q}~~\text{ for }~37\le q\le839.$ Moreover, we improve the lexi-bounds, applying randomized greedy algorithms, and show that $\ell_q(4,3)\le \ell_q(4,3,5)< 2.61\sqrt[3]{q\ln q}~\text{ if }~13\le q\le4373;$ $\ell_q(4,3)\le \ell_q(4,3,5)< 2.65\sqrt[3]{q\ln q}~\text{ if }~4373<q\le7057;$ $\ell_q(5,3)<2.785\sqrt[3]{q^2\ln q}~\text{ if }~11\le q\le401;$ $\ell_q(5,3)\le\ell_q(5,3,5)<2.884\sqrt[3]{q^2\ln q}~\text{ if }~401<q\le839.$ The codes, obtained in this paper by leximatrix and inverse leximatrix algorithms, provide new upper bounds (called density lexi-bounds) on the smallest covering density $μ_q(r,R)$ of a $q$ -ary linear code of codimension $r$ and covering radius $R$ : $μ_q(4,3)<3.3\cdot\ln q~~\text{ for }~11\le q\le7057;$ $μ_q(5,3)<4.2\cdot\ln q~~\text{ for }~37\le q\le839.$

preprint2016arXiv

On upper bounds on the smallest size of a saturating set in a projective plane

In a projective plane $Π_{q}$ (not necessarily Desarguesian) of order $q,$ a point subset $S$ is saturating (or dense) if any point of $Π_{q}\setminus S$ is collinear with two points in $~S$ . Using probabilistic methods, the following upper bound on the smallest size $s(2,q)$ of a saturating set in $Π_{q}$ is proved: \begin{equation*} s(2,q)\leq 2\sqrt{(q+1)\ln (q+1)}+2\thicksim 2\sqrt{q\ln q}. \end{equation*} We also show that for any constant $c\ge 1$ a random point set of size $k$ in $Π_{q}$ with $2c\sqrt{(q+1)\ln(q+1)}+2\le k<\frac{q^{2}-1}{q+2}\thicksim q$ is a saturating set with probability greater than $1-1/(q+1)^{2c^{2}-2}.$ Our probabilistic approach is also applied to multiple saturating sets. A point set $S\subset Π_{q}$ is $(1,μ)$ -saturating if for every point $Q$ of $Π_{q}\setminus S$ the number of secants of $S$ through $Q$ is at least $μ$ , counted with multiplicity. The multiplicity of a secant $\ell$ is computed as ${\binom{\#(\ell \,\cap S)}{2}}.$ The following upper bound on the smallest size $s_{μ}(2,q)$ of a $(1,μ)$ -saturating set in $Π_{q}$ is proved: \begin{equation*} s_{μ}(2,q)\leq 2(μ+1)\sqrt{(q+1)\ln (q+1)}+2\thicksim 2(μ+1)\sqrt{ q\ln q}\,\text{ for }\,2\leq μ\leq \sqrt{q}. \end{equation*} By using inductive constructions, upper bounds on the smallest size of a saturating set (as well as on a $(1,μ)$ -saturating set) in the projective space $PG(N,q)$ are obtained. All the results are also stated in terms of linear covering codes.

preprint2016arXiv

Tables, bounds and graphics of the smallest known sizes of complete caps in the spaces $\mathrm{PG}(3,q)$ and $\mathrm{PG}(4,q)$

In this paper we present and analyze computational results concerning small complete caps in the projective spaces $\mathrm{PG}(N,q)$ of dimension $N=3$ and $N=4$ over the finite field of order $q$ . The results have been obtained using randomized greedy algorithms and the algorithm with fixed order of points (FOP). The computations have been done in relatively wide regions of $q$ values; such wide regions are not considered in literature for $N=3,4$ . The new complete caps are the smallest known. Basing on them, we obtained new upper bounds on $t_2(N,q)$ , the minimum size of a complete cap in $\mathrm{PG}(N,q)$ , in particular, \begin{align*} &t_{2}(N,q)<\sqrt{N+2}\cdot q^{\frac{N-1}{2^{\vphantom{H}}}}\sqrt{\ln q},\quad q\in L_{N},\quad N=3,4,\\ &t_{2}(N,q)<\left(\sqrt{N+1}+\frac{1.3}{\ln (2q)}\right)q^{\frac{N-1}{2^{\vphantom{H}}}}\sqrt{\ln q},\quad q\in L_{N},\quad N=3,4, \end{align*} where \begin{align*} &L_{3}:=\{q\le 4673, ~q\ \textrm{prime}\} \cup \{5003,6007,7001,8009\},\\ &L_{4}:=\{q\le 1361, ~q\ \textrm{prime}\} \cup \{1409\}. \end{align*} Our investigations and results allow to conjecture that these bounds hold for all $q$ .

preprint2015arXiv

Further results on multiple coverings of the farthest-off points

Multiple coverings of the farthest-off points ( $(R,μ)$ -MCF codes) and the corresponding $(ρ,μ)$ -saturating sets in projective spaces $PG(N,q)$ are considered. We propose and develop some methods which allow us to obtain new small $(1,μ)$ -saturating sets and short $(2,μ)$ -MCF codes with $μ$ -density either equal to 1 (optimal saturating sets and almost perfect MCF-codes) or close to 1 (roughly $1+1/cq$ , $c\ge1$ ). In particular, we provide new algebraic constructions and some bounds. Also, we classify minimal and optimal $(1,μ)$ -saturating sets in $PG(2,q)$ , $q$ small.

preprint2015arXiv

Tables, bounds and graphics of the smallest known sizes of complete arcs in the plane $\mathrm{PG}(2,q)$ for all $q\le160001$ and sporadic $q$ in the interval $[160801\ldots 430007]$

In the projective planes $\mathrm{PG}(2,q)$ , we collect the smallest known sizes of complete arcs for the regions \begin{align*} &\mbox{all } q\le160001,~~ q \mbox{ prime power};\\ &Q_{4}=\{34 \mbox{ sporadic }q'\mbox{s in the interval }[160801\ldots430007], \mbox{ see Table 3}\}. \end{align*} For $q\le160001$ , the collection of arc sizes is complete in the sense that arcs for all prime powers are considered. This proves new upper bounds on the smallest size $t_{2}(2,q)$ of a complete arc in $\mathrm{PG}(2,q)$ , in particular \begin{align*} t_{2}(2,q)&<0.998\sqrt{3q\ln q}<1.729\sqrt{q\ln q}&\mbox{ for }&&7&\le q\le160001;~~(1) \\ t_{2}(2,q)&<\sqrt{q}\ln^{0.7295}q&\mbox{ for }&&109&\le q\le160001;~~(2)\\ t_{2}(2,q)&<\sqrt{q}\ln^{c_{up}(q)}q,~~c_{up}(q)=\frac{0.27}{\ln q}+0.7,&\mbox{ for }&&19&\le q\le160001;~~(3)\\ t_{2}(2,q)&<0.6\sqrt{q}\ln^{φ_{up}(q;0.6)} q,~~φ_{up}(q;0.6)=\frac{1.5}{\ln q}+0.802,&\mbox{ for }&&19&\le q\le160001.~~(4) \end{align*} Moreover, the bounds (2) -- (4) hold also for $q\in Q_{4}$ . Also, \begin{align*} t_{2}(2,q)&<1.006\sqrt{3q\ln q}<1.743\sqrt{q\ln q}&\mbox{ for }&&q\in Q_{4}.~~(5) \end{align*} Our investigations and results allow to conjecture that the bounds (2) -- (5) hold for all $q\geq109$ .

preprint2014arXiv

Tables of parameters of symmetric configurations $v_{k}$

Tables of the currently known parameters of symmetric configurations are given. Formulas for parameters of the known infinite families of symmetric configurations are presented as well. The results of the recent paper [18] are used. This work can be viewed as an appendix to [18], in the sense that the tables given here cover a much larger set of parameters.

preprint2014arXiv

Tables of sizes of random complete arcs in the plane $PG(2,q)$

Tables of sizes of random complete arcs in the plane $PG(2,q)$ are given. The sizes are close to the smallest known sizes of complete arcs in $PG(2,q)$ , in particular, to ones constructed by Algorithm FOP (fixed order of points). The random arcs are obtained in the region $\{3\leq q\leq 46337,~q \mbox{prime}\}$.

preprint2012arXiv

On constructions and parameters of symmetric configurations v_{k}

The spectrum of possible parameters of symmetric configurations is investigated. We both survey known constructions and results, and propose some new construction methods. Many new parameters are obtained, in particular for cyclic symmetric configurations, which are equivalent to deficient cyclic difference sets. Both Golomb rulers and modular Golomb rulers are a key tool in our investigation. Several new upper bounds on the minimum integer E(k) such that for each v >= E(k) there exists a symmetric configuration v_{k} are obtained. Upper bounds of the same type are provided for cyclic symmetric configurations. From the standpoint of applications, it should be noted that our results extend the range of possible parameters of LDPC codes, generalized LDPC codes, and quasi-cyclic LDPC codes.

preprint2011arXiv

On sizes of complete arcs in PG(2,q)

New upper bounds on the smallest size t_{2}(2,q) of a complete arc in the projective plane PG(2,q) are obtained for 853 <= q <= 4561 and q\in T1\cup T2 where T1={173,181,193,229,243,257,271,277,293,343,373,409,443,449,457, 461,463,467,479,487,491,499,529,563,569,571,577,587,593,599,601,607,613,617,619,631, 641,661,673,677,683,691, 709}, T2={4597,4703,4723,4733,4789,4799,4813,4831,5003,5347,5641,5843,6011,8192}. From these new bounds it follows that for q <= 2593 and q=2693,2753, the relation t_{2}(2,q) < 4.5\sqrt{q} holds. Also, for q <= 4561 we have t_{2}(2,q) < 4.75\sqrt{q}. It is showed that for 23 <= q <= 4561 and q\in T2\cup {2^{14},2^{15},2^{18}}, the inequality t_{2}(2,q) < \sqrt{q}ln^{0.75}q is true. Moreover, the results obtained allow us to conjecture that this estimate holds for all q >= 23. The new upper bounds are obtained by finding new small complete arcs with the help of a computer search using randomized greedy algorithms. Also new constructions of complete arcs are proposed. These constructions form families of k-arcs in PG(2,q) containing arcs of all sizes k in a region k_{min} <= k <= k_{max} where k_{min} is of order q/3 or q/4 while k_{max} has order q/2. The completeness of the arcs obtained by the new constructions is proved for q <= 1367 and 2003 <= q <= 2063. There is reason to suppose that the arcs are complete for all q > 1367. New sizes of complete arcs in PG(2,q) are presented for 169 <= q <= 349 and q=1013,2003.

preprint2011arXiv

Upper bounds on the smallest size of a complete arc in the plane PG(2,q)

New upper bounds on the smallest size t_{2}(2,q) of a complete arc in the projective plane PG(2,q) are obtained for q <= 9109. From these new bounds it follows that for q <= 2621 and q = 2659,2663,2683,2693,2753,2801, the relation t_{2}(2,q) < 4.5\sqrt{q} holds. Also, for q <= 5399 and q = 5413,5417,5419,5441,5443,5471,5483,5501,5521, we have t_{2}(2,q) < 4.8\sqrt{q}. Finally, for q <= 9067 it holds that t_{2}(2,q) < 5\sqrt{q}. The new upper bounds are obtained by finding new small complete arcs with the help of a computer search using randomized greedy algorithms.

preprint2010arXiv

New sizes of complete arcs in PG(2,q)

New upper bounds on the smallest size t_{2}(2,q) of a complete arc in the projective plane PG(2,q) are obtained for 853<= q<= 2879 and q=3511,4096, 4523,5003,5347,5641,5843,6011. For q<= 2377 and q=2401,2417,2437, the relation t_{2}(2,q)<4.5\sqrt{q} holds. The bounds are obtained by finding of new small complete arcs with the help of computer search using randomized greedy algorithms. Also new sizes of complete arcs are presented.

Alexander A. Davydov

Research overview

Is this your work?

16 publications

Orbits of the class $\mathcal{O}_6$ of lines external with respect to the twisted cubic in $\mathrm{PG}(3,q)$

On cosets weight distributions of the doubly-extended Reed-Solomon codes of codimension 4

Twisted cubic and orbits of lines in $\mathrm{PG}(3,q)$ , II

On integral weight spectra of the MDS codes cosets of weight 1, 2, and 3

On planes through points off the twisted cubic in $\mathrm{PG}(3,q)$ and multiple covering codes

Tables, bounds and graphics of short linear codes with covering radius 3 and codimension 4 and 5

On upper bounds on the smallest size of a saturating set in a projective plane

Tables, bounds and graphics of the smallest known sizes of complete caps in the spaces $\mathrm{PG}(3,q)$ and $\mathrm{PG}(4,q)$

Further results on multiple coverings of the farthest-off points

Tables, bounds and graphics of the smallest known sizes of complete arcs in the plane $\mathrm{PG}(2,q)$ for all $q\le160001$ and sporadic $q$ in the interval $[160801\ldots 430007]$

Tables of parameters of symmetric configurations $v_{k}$

Tables of sizes of random complete arcs in the plane $PG(2,q)$

On constructions and parameters of symmetric configurations v_{k}

On sizes of complete arcs in PG(2,q)

Upper bounds on the smallest size of a complete arc in the plane PG(2,q)

New sizes of complete arcs in PG(2,q)

See the researcher in context

Building this map preview

Alexander A. Davydov

Research overview

Is this your work?

16 publications

Orbits of the class O6\mathcal{O}_6O6​ of lines external with respect to the twisted cubic in PG(3,q)\mathrm{PG}(3,q)PG(3,q)

On cosets weight distributions of the doubly-extended Reed-Solomon codes of codimension 4

Twisted cubic and orbits of lines in PG(3,q)\mathrm{PG}(3,q)PG(3,q), II

On integral weight spectra of the MDS codes cosets of weight 1, 2, and 3

On planes through points off the twisted cubic in PG(3,q)\mathrm{PG}(3,q)PG(3,q) and multiple covering codes

Tables, bounds and graphics of short linear codes with covering radius 3 and codimension 4 and 5

On upper bounds on the smallest size of a saturating set in a projective plane

Tables, bounds and graphics of the smallest known sizes of complete caps in the spaces PG(3,q)\mathrm{PG}(3,q)PG(3,q) and PG(4,q)\mathrm{PG}(4,q)PG(4,q)

Further results on multiple coverings of the farthest-off points

Tables, bounds and graphics of the smallest known sizes of complete arcs in the plane PG(2,q)\mathrm{PG}(2,q)PG(2,q) for all q≤160001q\le160001q≤160001 and sporadic qqq in the interval [160801…430007][160801\ldots 430007][160801…430007]

Tables of parameters of symmetric configurations vkv_{k}vk​

Tables of sizes of random complete arcs in the plane PG(2,q)PG(2,q)PG(2,q)

On constructions and parameters of symmetric configurations v_{k}

On sizes of complete arcs in PG(2,q)

Upper bounds on the smallest size of a complete arc in the plane PG(2,q)

New sizes of complete arcs in PG(2,q)

See the researcher in context

Building this map preview

Orbits of the class $\mathcal{O}_6$ of lines external with respect to the twisted cubic in $\mathrm{PG}(3,q)$

Twisted cubic and orbits of lines in $\mathrm{PG}(3,q)$ , II

On planes through points off the twisted cubic in $\mathrm{PG}(3,q)$ and multiple covering codes

Tables, bounds and graphics of the smallest known sizes of complete caps in the spaces $\mathrm{PG}(3,q)$ and $\mathrm{PG}(4,q)$

Tables, bounds and graphics of the smallest known sizes of complete arcs in the plane $\mathrm{PG}(2,q)$ for all $q\le160001$ and sporadic $q$ in the interval $[160801\ldots 430007]$

Tables of parameters of symmetric configurations $v_{k}$

Tables of sizes of random complete arcs in the plane $PG(2,q)$