BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
Let q,n≥1 be integers, [q]={1,…,q}, and F be a field with ∣F∣≥q. The set of increasing sequences I(n,q)={(f1,f2,…,fn)∈[q]n: f1≤f2≤⋯≤fn} can be mapped via an injective map i:[q]→F into a subset J(n,q) of the affine space Fn. We describe reduced Gröbner bases, standard monomials and Hilbert function of the ideal of polynomials vanishing on J(n,q). As applications we give an interpolation basis for J(n,q), and lower bounds for the size of increasing Kakeya sets, increasing Nikodym sets, and for the size of affine hyperplane covers of J(n,q).
In a recent paper Petrov and Pohoata developed a new algebraic method which combines the Croot-Lev-Pach Lemma from additive combinatorics and Sylvester's Law of Inertia for real quadratic forms. As an application, they gave a simple proof of the Bannai-Bannai-Stanton bound on the size of s-distance sets (subsets $\mbox{$\cal A$}\subseteq {\mathbb R}^n$ which determine at most s different distances). In this paper we extend their work and prove upper bounds for the size of s-distance sets in various real algebraic sets. This way we obtain a novel and short proof for the bound of Delsarte-Goethals-Seidel on spherical s-distance sets and a generalization of a bound by Bannai-Kawasaki-Nitamizu-Sato on s-distance sets on unions of spheres. In our arguments we use the method of Petrov and Pohoata together with some Gröbner basis techniques.
We propose a polynomial time f-algorithm (a deterministic algorithm which uses an oracle for factoring univariate polynomials over Fq) for computing an isomorphism (if there is any) of a finite dimensional Fq(x)-algebra A given by structure constants with the algebra of n by n matrices with entries from Fq(x). The method is based on computing a finite Fq-subalgebra of A which is the intersection of a maximal Fq[x]-order and a maximal R-order, where R is the subring of Fq(x) consisting of fractions of polynomials with denominator having degree not less than that of the numerator.
We say that a set system F⊆2[n] shatters a given set S⊆[n] if 2S={F∩S:F∈F}. The Sauer inequality states that in general, a set system F shatters at least ∣F∣ sets. Here we concentrate on the case of equality. A set system is called shattering-extremal if it shatters exactly ∣F∣ sets. In this paper we characterize shattering-extremal set systems of Vapnik-Chervonenkis dimension 2 in terms of their inclusion graphs, and as a corollary we answer an open question from \cite{VC1} about leaving out elements from shattering-extremal set systems in the case of families of Vapnik-Chervonenkis dimension 2.
Let $\K$ be an algebraic number field of degree d and discriminant Δ over $\Q$. Let $\A$ be an associative algebra over $\K$ given by structure constants such that $\A\cong M_n(\K)$ holds for some positive integer n. Suppose that d, n and ∣Δ∣ are bounded. In a previous paper a polynomial time ff-algorithm was given to construct explicitly an isomorphism $\A \rightarrow M_n(\K)$. Here we simplify and improve this algorithm in the cases n≤43, $\K=\Q$, and n=2, with $\K=\Q(\sqrt{-1})$ or $\K=\Q(\sqrt{-3})$. The improvements are based on work by Y. Kitaoka and R. Coulangeon on tensor products of lattices.
We say that a set system F⊆2[n] shatters a given set S⊆[n] if 2S=F∩S:F∈F. The Sauer inequality states that in general, a set system F shatters at least ∣F∣ sets. Here we concentrate on the case of equality. A set system is called shattering-extremal if it shatters exactly ∣F∣ sets. We characterize shattering extremal set systems of Vapnik-Chervonenkis dimension 1 in terms of their inclusion graphs. Also from the perspective of extremality, we relate set systems of bounded Vapnik-Chervonenkis dimension to their projections.
Alon's combinatorial Nullstellensatz (Theorem 1.1 from \cite{Alon1}) is one of the most powerful algebraic tools in combinatorics, with a diverse array of applications. Let $\F$ be a field, S1,S2,...,Sn be finite nonempty subsets of $\F$. Alon's theorem is a specialized, precise version of the Hilbertsche Nullstellensatz for the ideal of all polynomial functions vanishing on the set $S=S_1\times S_2\times ... \times S_n\subseteq \F^n$. From this Alon deduces a simple and amazingly widely applicable nonvanishing criterion (Theorem 1.2 in \cite{Alon1}). It provides a sufficient condition for a polynomial f(x1,...,xn) which guarantees that f is not identically zero on the set S. In this paper we extend these two results from sets of points to multisets. We give two different proofs of the generalized nonvanishing theorem. We extend some of the known applications of the original nonvanishing theorem to a setting allowing multiplicities, including the theorem of Alon and Füredi on the hyperplane coverings of discrete cubes.
Alon's combinatorial Nullstellensatz, and in particular the resulting nonvanishing criterion is one of the most powerful algebraic tools in combinatorics, with many important applications. In this paper we extend the nonvanishing theorem in two directions. We prove a version allowing multiple points. Also, we establish a variant which is valid over arbitrary commutative rings, not merely over subrings of fields. As an application, we prove extensions of the theorem of Alon and Füredi on hyperplane coverings of discrete cubes.
Let K be an algebraic number field of degree d and discriminant D over Q. Let A be an associative algebra over K given by structure constants such that A is isomorphic to the algebra M_n(K) of n by n matrices over K for some positive integer n. Suppose that d, n and D are bounded. Then an isomorphism of A with M_n(K) can be constructed by a polynomial time ff-algorithm. (An ff-algorithm is a deterministic procedure which is allowed to call oracles for factoring integers and factoring univariate polynomials over finite fields.) As a consequence, we obtain a polynomial time ff-algorithm to compute isomorphisms of central simple algebras of bounded degree over K.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.