On Maximal Families of Binary Polynomials with Pairwise Linear Common Factors

• URL: http://arxiv.org/abs/2405.08741v1
• Date: Tue, 14 May 2024 16:30:28 GMT
• Title: On Maximal Families of Binary Polynomials with Pairwise Linear Common Factors
• Authors: Maximilien Gadouleau, Luca Mariot, Federico Mazzone,
• Abstract summary: We characterize maximal families over the binary field $mathbbF$. Our findings prompt several more open questions, which we plan to address in an extended version of this work.
• Score: 1.249418440326334
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the construction of maximal families of polynomials over the finite field $\mathbb{F}_q$, all having the same degree $n$ and a nonzero constant term, where the degree of the GCD of any two polynomials is $d$ with $1 \le d\le n$. The motivation for this problem lies in a recent construction for subspace codes based on cellular automata. More precisely, the minimum distance of such subspace codes relates to the maximum degree $d$ of the pairwise GCD in this family of polynomials. Hence, characterizing the maximal families of such polynomials is equivalent to determining the maximum cardinality of the corresponding subspace codes for a given minimum distance. We first show a lower bound on the cardinality of such families, and then focus on the specific case where $d=1$. There, we characterize the maximal families of polynomials over the binary field $\mathbb{F}_2$. Our findings prompt several more open questions, which we plan to address in an extended version of this work.

Related papers

• On lower bounds of the density of planar periodic sets without unit distances [55.2480439325792]
  We introduce a novel approach to estimating $m_1(mathbbR2)$ by reformulating the problem as a Maximal Independent Set (MIS) problem on graphs constructed from flat torus. Our experimental results supported by theoretical justifications of proposed method demonstrate that for a sufficiently wide range of parameters this approach does not improve the known lower bound.
  arXiv  Detail & Related papers  (2024-11-20T12:07:19Z)
• Fast Multiplication and the PLWE-RLWE Equivalence for an Infinite Family of Cyclotomic Subextensions [6.487242614495099]
  We prove the equivalence between the Ring Learning With Errors (RLWE) and the Polynomial Learning With Errors (PLWE) problems. We also describe a fast integers for computing the product of two elements in the ring of the maximal real subfield.
  arXiv  Detail & Related papers  (2024-10-01T15:32:02Z)
• Bridging Weighted First Order Model Counting and Graph Polynomials [6.2686964302152735]
  We use Weak Connectedness Polynomial and Strong Connectedness Polynomials for first-order logic sentences. We can use them to solve WFOMC with all of the existing axioms known to be tractable.
  arXiv  Detail & Related papers  (2024-07-16T16:01:25Z)
• Higher Level Completeness for Permutation Polynomials [0.0]
  Generalising the concept of a complete permutation over a finite field, we define completness to level $kge1$ in fields of odd characteristics. We construct two families of characteristics that satisfy the condition of high level completeness for all finite fields.
  arXiv  Detail & Related papers  (2023-10-19T04:47:53Z)
• Dimension-free Remez Inequalities and norm designs [48.5897526636987]
  A class of domains $X$ and test sets $Y$ -- termed emphnorm -- enjoy dimension-free Remez-type estimates. We show that the supremum of $f$ does not increase by more than $mathcalO(log K)2d$ when $f$ is extended to the polytorus.
  arXiv  Detail & Related papers  (2023-10-11T22:46:09Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  In this paper, we demonstrate an exponential separation between exact degree and approximate quantum query for a partial function. For an alphabet size, we have a constant versus separation complexity.
  arXiv  Detail & Related papers  (2023-01-22T22:08:28Z)
• Progressive approximation of bound states by finite series of square-integrable functions [0.0]
  We use the "tridiagonal representation approach" to solve the time-independent Schr"odinger equation for bound states in a basis set of finite size.
  arXiv  Detail & Related papers  (2022-02-20T00:25:35Z)
• Density theorems with applications in quantum signal processing [0.0]
  We study the approximation capabilities of two families of univariates that arise in applications of quantum signal processing. We propose two subfamilies of monotone and non-monotone approximations. For the non-monotone case, under some additional assumptions, we provide an iterative algorithm that finds the optimal approximation.
  arXiv  Detail & Related papers  (2021-11-13T20:00:21Z)
• Small Covers for Near-Zero Sets of Polynomials and Learning Latent Variable Models [56.98280399449707]
  We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$. Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
  arXiv  Detail & Related papers  (2020-12-14T18:14:08Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  We introduce finite-function-encoding (FFE) states which encode arbitrary $d$-valued logic functions. We investigate some of their structural properties.
  arXiv  Detail & Related papers  (2020-12-01T13:53:23Z)
• Optimal Low-Degree Hardness of Maximum Independent Set [93.59919600451487]
  We study the algorithmic task of finding a large independent set in a sparse ErdHos-R'enyi random graph. We show that the class of low-degree algorithms can find independent sets of half-optimal size but no larger.
  arXiv  Detail & Related papers  (2020-10-13T17:26:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.