Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract In this paper we go further with the study initiated by Behle, Krebs and Reifferscheid (in: Proceedings CAI 2011, Lecture Notes in Computer Science, vol 6742, pp 97–114, 2011), who gave an Eilenberg-type theorem for non-regular languages via typed monoids. We provide a new extension of that result, inspired by the one carried out by Pin in the regular case in 1995, who considered classes of languages not necessarily closed under complement. We introduce the so-called positively typed monoids, and give a correspondence between varieties of such algebraic structures and positive varieties of possibly non-regular languages. We also prove a similar result for classes of languages with weaker closure properties. PubDate: 2021-11-01 DOI: 10.1007/s00200-020-00414-2

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract In this paper, we start with a discussion of discrete Gaussian measures on lattices. Several results of Banaszczyk are analyzed, a simple form of uncertainty principle for discrete Gaussian measure is formulated. In the second part of the paper we prove two new bounds for the smoothing parameter of lattices. Under the natural assumption that \(\varepsilon\) is suitably small, we obtain two estimations of the smoothing parameter: $$\begin{aligned} \displaystyle \eta _{\varepsilon }({{\mathbb {Z}}}) \le \sqrt{\frac{\ln \big (\frac{\varepsilon }{44}+\frac{2}{\varepsilon }\big )}{\pi }}. \end{aligned}$$ This is a practically useful case. For this case, our upper bound is very close to the exact value of \(\eta _{\varepsilon }({{\mathbb {Z}}})\) in that \(\sqrt{\frac{\ln \big (\frac{\varepsilon }{44}+\frac{2}{\varepsilon }\big )}{\pi }}-\eta _{\varepsilon }({{\mathbb {Z}}})\le \frac{\varepsilon ^2}{552}\) . For a lattice \({{{\mathcal {L}}}}\subset {{\mathbb {R}}}^n\) of dimension n, $$\begin{aligned} \displaystyle \eta _{\varepsilon }({{{\mathcal {L}}}}) \le \sqrt{\frac{\ln \big (n-1+\frac{2n}{\varepsilon }\big )}{\pi }}\tilde{bl}({{{\mathcal {L}}}}). \end{aligned}$$ PubDate: 2021-11-01 DOI: 10.1007/s00200-020-00417-z

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Let \(R={\mathbb {F}}_{q^2}+u{\mathbb {F}}_{q^2}+\cdots +u^{r-1}{\mathbb {F}}_{q^2}\) be a finite non-chain ring, where q is a prime power, \(u^{r}=1\) and \(r (q+1)\) . In this paper, we study u-constacyclic codes over the ring R. Using the matrix of Fourier transform, a Gray map from R to \({\mathbb {F}}_{q^2}^{r}\) is given. Under the special Gray map, we show that the image of Gray map of u-constacyclic codes over R are cyclic codes over \({\mathbb {F}}_{q^2}\) , and some new quantum codes are obtained via the Gray map and Hermitian construction from Hermitian dual-containing u-constacyclic codes. PubDate: 2021-11-01 DOI: 10.1007/s00200-020-00415-1

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract The class of reduction-based algorithms was introduced recently as a new approach towards creative telescoping. Starting with Hermite reduction of rational functions, various reductions have been introduced for increasingly large classes of holonomic functions. In this paper we show how to construct reductions for general holonomic functions, in the purely differential setting. PubDate: 2021-11-01 DOI: 10.1007/s00200-020-00413-3

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract In this paper, we study cyclic codes and their duals over the local Frobenius non-chain ring \(R={\mathbb {F}}_2[u,v] / \langle u^2=v^2,uv \rangle \) , and we obtain optimal binary linear codes with respect to the homogeneous weight over R via a Gray map. Moreover, we characterize DNA codes as images of cyclic codes over R. PubDate: 2021-11-01 DOI: 10.1007/s00200-020-00416-0

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Linear codes with complementary duals (shortly named LCD codes) are linear codes whose intersection with their duals are trivial. In this paper, we give a method of constructing these type of linear codes from equitable partitions of association schemes. The LCD codes constructed in this paper are of length 2n and dimension n and have the property of being formally self-dual. To illustrate the method we construct LCD codes from some distance-regular graphs. PubDate: 2021-10-05 DOI: 10.1007/s00200-021-00532-5

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract An \((n, k, d, \alpha )\) -MSR (minimum storage regeneration) code is a set of n nodes used to store a file. For a file of total size \(k\alpha\) , each node stores \(\alpha\) symbols, any k nodes determine the file, and any d nodes can repair any other node by each sending out \(\alpha /(d-k+1)\) symbols. In this work, we express the product-matrix construction of \(\bigl (n, k, 2(k-1), k-1\bigr )\) -MSR codes in terms of symmetric algebras. We then generalize the product-matrix construction to \(\bigl (n, k, \frac{(k-1)t}{t-1}, \left( {\begin{array}{c}k-1\\ t-1\end{array}}\right) \bigr )\) -MSR codes for general \(t\geqslant 2\) , while the \(t=2\) case recovers the product-matrix construction. Our codes’ sub-packetization level— \(\alpha\) —is small and independent of n. It is less than \(L^{2.8(d-k+1)}\) , where L is Alrabiah–Guruswami’s lower bound on \(\alpha\) . Furthermore, it is less than other MSR codes’ \(\alpha\) for a set of practical parameters. Finally, we discuss how our code repairs multiple failures at once. PubDate: 2021-10-01 DOI: 10.1007/s00200-021-00526-3

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Linear codes constructed from defining sets have been extensively studied since they may have good parameters if the defining sets are chosen properly. Let \(\mathbb{F}_{p^m}\) be the finite field with \(p^m\) elements, where p is an odd prime and m is a positive integer. In this paper, we study the linear code \({\mathcal {C}}_D=\{ (\mathrm{Tr}(\alpha x))_{x \in D}\, \, \alpha \in {\mathbb {F}}_{p^m}\}\) by choosing the defining set \(D=\{x \in {\mathbb {F}}_{p^m}^*\, \, \mathrm{Tr}(ax^2+bx)=0\}\) , where \(a\in {\mathbb {F}}_{p^m}^*\) and \(b \in {\mathbb {F}}_{p^m}\) . Several classes of linear codes with explicit weight distribution are obtained. The parameters of some proposed codes are new. Several examples show that some of our codes are optimal or almost optimal according to the tables of best codes known in Grassl. Our results generalize some results in Ding and Ding (IEEE Trans. Inf. Theory 61(11):5835–5842, 2015), Li et al. (Disc. Math. 241:25–38, 2018). PubDate: 2021-09-27 DOI: 10.1007/s00200-021-00527-2

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Can we factor an integer \(N\) unconditionally, in deterministic polynomial time, given the value of its Euler totient \(\varphi (N)\) ' We show that this can be done under certain size conditions on the prime factors of \(N\) . The key technique is lattice basis reduction using the LLL algorithm. Among our results, we show that if \(N\) has a prime factor \(p > \sqrt{N}\) , then we can recover \(p\) in deterministic polynomial time given \(\varphi (N)\) . We also shed some light on the analogous factorization problems given oracles for the sum-of-divisors function, Carmichael’s function, and the order oracle that is used in Shor’s quantum factoring algorithm. PubDate: 2021-09-16 DOI: 10.1007/s00200-021-00521-8

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Cyclic codes are among the most important families of codes in coding theory for both theoretical and practical reasons. Despite their prominence and intensive research on cyclic codes for over a half century, there are still open problems related to cyclic codes. In this work, we use recent results on the equivalence of cyclic codes to create a more efficient algorithm to partition cyclic codes by equivalence based on cyclotomic cosets. This algorithm is then implemented to carry out computer searches for both cyclic codes and quasi-cyclic (QC) codes with good parameters. We also generalize these results to repeated-root cases. We have found several new linear codes that are cyclic or QC as an application of the new approach, as well as more desirable constructions for linear codes with best known parameters. With the additional new codes obtained through standard constructions, we have found a total of 14 new linear codes. PubDate: 2021-09-06 DOI: 10.1007/s00200-021-00525-4

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract In Beelen and Montanucci (Finite Fields Appl 52:10–29, 2018) and Giulietti and Korchmáros (Math Ann 343:229–245, 2009), Weierstrass semigroups at points of the Giulietti–Korchmáros curve \({\mathcal {X}}\) were investigated and the sets of minimal generators were determined for all points in \({\mathcal {X}}(\mathbb {F}_{q^2})\) and \({\mathcal {X}}(\mathbb {F}_{q^6})\setminus {\mathcal {X}}( \mathbb {F}_{q^2})\) . This paper completes their work by settling the remaining cases, that is, for points in \({\mathcal {X}}(\overline{\mathbb {F}}_{q}){\setminus }{\mathcal {X}}( \mathbb {F}_{q^6})\) . As an application to AG codes, we determine the dimensions and the lengths of duals of one-point codes from a point in \({\mathcal {X}}(\mathbb {F}_{q^7}){\setminus }{\mathcal {X}}( \mathbb {F}_{q})\) and we give a bound on the Feng–Rao minimum distance \(d_{ORD}\) . For \(q=3\) we provide a table that also reports the exact values of \(d_{ORD}\) . As a further application we construct quantum codes from \(\mathbb {F}_{q^7}\) -rational points of the GK-curve. PubDate: 2021-09-04 DOI: 10.1007/s00200-021-00519-2

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Discrete logarithm problem (DLP) and Conjugacy search problem (CSP) are two important tools for designing public key protocols. However DLP is used over commutative as well as non-commutative platforms but CSP is used only over non-commutative platforms. To harden the security of cryptosystems using DLP and CSP as base problems, various authors have combined these two problems to form a new problem called Discrete logarithm with conjugacy search problem (DLCSP). It has been used to design key exchange protocols and signature schemes over the general linear group with entries from group ring, that is, \(GL_n(\mathbb {F}_q[S_r])\) . In this paper, we show that, if someone can solve DLP in polynomial time over some finite extension of \(\mathbb {F}_q\) , then DLCSP over \(GL_n(\mathbb {F}_q[S_r])\) can also be solved in polynomial time with non-negligible probability. PubDate: 2021-08-30 DOI: 10.1007/s00200-021-00523-6

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Inspired by the fundamental work of Lechuga and Murillo (Topology 39:89–94, 2000) who established a connection between graph theory and rational homotopy theory, this paper defines new algebraic invariants for a non-oriented, simple, connected and finite graph G namely the rational cohomology \(H^*(G)\) , the Lusternik-Schnirelmann category cat(G), the cohomology Euler-Poincaré characteristic \(\chi _G\) , the Koszul-Poincare series \({{\mathcal {U}}}_{G}(z)\) and the formal dimension fd(G). Moreover we compute those invariants by exploiting some deep well known theorems from rational homotopy theory. PubDate: 2021-08-21 DOI: 10.1007/s00200-021-00522-7

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract In this paper we characterize the c-Boomerang Connectivity Table (BCT), \(c\ne 0\) (thus, including the classical \(c=1\) case), for all monomial function \(x^d\) in terms of characters and Weil sums on the finite field \({\mathbb F}_{p^n}\) , for an odd prime p. We further simplify these expressions for the Gold functions \(x^{p^k+1}\) for all \(1\le k<n\) , and p odd. It is the first such attempt for a complete description for the classical BCT and its relative c-BCT, for all parameters involved, albeit in terms of characters. PubDate: 2021-08-06 DOI: 10.1007/s00200-021-00520-9

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Linear codes with a few weights have nice applications in communication, secret sharing schemes, authentication codes, association schemes, block designs and so on. Projective binary linear codes are one of the most important subclasses of linear codes for practical applications. The objective of this paper is to construct projective binary linear codes with some special Boolean functions. Four families of binary linear codes with three or four weights are derived and the parameters of their duals are also determined. It turns out that the duals of these codes are optimal or almost optimal with respect to the sphere-packing bound. As applications, the codes presented in this paper can be used to construct association schemes and secret sharing schemes with interesting access structures. PubDate: 2021-08-01 DOI: 10.1007/s00200-019-00412-z

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract In this paper we show that the \({\mathbb {Z}}/p^{m}{\mathbb {Z}}\) -module structure of the ring \(E_p^{(m)}\) is isomorphic to a \({\mathbb {Z}}/p^{m}{\mathbb {Z}}\) -submodule of the matrix ring over \({\mathbb {Z}}/p^{m}{\mathbb {Z}}\) . Using this intrinsic structure of \(E_p^{(m)}\) , solving a linear system over \(E_p^{(m)}\) becomes computationally equivalent to solving a linear system over \({\mathbb {Z}}/p^{m}{\mathbb {Z}}\) . As an application we break the protocol based on the Diffie–Hellman decomposition problem and ElGamal decomposition problem over \(E_p^{(m)}\) . Our algorithm terminates in a provable running time of \(O(m^{6})\) \({\mathbb {Z}}/p^{m}{\mathbb {Z}}\) -operations. PubDate: 2021-08-01 DOI: 10.1007/s00200-019-00410-1

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract Let \(\mathbb {F}_{2^m}\) be a finite field of \(2^m\) elements and denote \(R=\mathbb {F}_{2^m}[u]/\langle u^k\rangle \) \(=\mathbb {F}_{2^m}+u\mathbb {F}_{2^m}+\cdots +u^{k-1}\mathbb {F}_{2^m}\) ( \(u^k=0\) ), where k is an integer satisfying \(k\ge 2\) . For any odd positive integer n, an explicit representation for every self-dual cyclic code over R of length 2n and a mass formula to count the number of these codes are given. In particular, a generator matrix is provided for the self-dual 2-quasi-cyclic code of length 4n over \(\mathbb {F}_{2^m}\) derived by an arbitrary self-dual cyclic code of length 2n over \(\mathbb {F}_{2^m}+u\mathbb {F}_{2^m}\) and a Gray map from \(\mathbb {F}_{2^m}+u\mathbb {F}_{2^m}\) onto \(\mathbb {F}_{2^m}^2\) . Finally, the hull of each cyclic code with length 2n over \(\mathbb {F}_{2^m}+u\mathbb {F}_{2^m}\) is determined and all distinct self-orthogonal cyclic codes of length 2n over \(\mathbb {F}_{2^m}+u\mathbb {F}_{2^m}\) are listed. PubDate: 2021-08-01 DOI: 10.1007/s00200-019-00408-9

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract In this note we present explicit examples of maximal and minimal curves over finite fields in odd characteristic. The curves are of Artin–Schreier type and the construction is closely related to quadratic forms from \({\mathbb {F}}_{q^n}\) to \({\mathbb {F}}_q\) . PubDate: 2021-08-01 DOI: 10.1007/s00200-019-00411-0

Please help us test our new pre-print finding feature by giving the pre-print link a rating. A 5 star rating indicates the linked pre-print has the exact same content as the published article.

Abstract: Abstract We examine the binary codes from the adjacency matrices of various products of graphs, and show that if the binary codes of a set of graphs have the property that their dual codes are the codes of the associated reflexive graphs, and are thus LCD, i.e. have zero hull, then, with some restrictions, the binary code of the product will have the same property. The codes are candidates for decoding using this property, or also, in the case of the direct product, by permutation decoding. PubDate: 2021-06-25 DOI: 10.1007/s00200-021-00517-4