Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn zeros of a polynomial in a finite grid
54
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A 1993 result of Alon and Furedi gives a sharp upper bound on the number of zeros of a multivariate polynomial over an integral domain in a finite grid, in terms of the degree of the polynomial. This result was recently generalized to polynomials over an arbitrary commutative ring, assuming a certain Condition (D) on the grid which holds vacuously when the ring is a domain. In the first half of this paper we give a further Generalized Alon-Furedi Theorem which provides a sharp upper bound when the degrees of the polynomial in each variable are also taken into account. This yields in particular a new proof of Alon-Furedi. We then discuss the relationship between Alon-Furedi and results of DeMillo-Lipton, Schwartz and Zippel. A direct coding theoretic interpretation of Alon-Furedi Theorem and its generalization in terms of Reed--Muller type affine variety codes is shown which gives us the minimum Hamming distance of these codes. Then we apply the Alon-Furedi Theorem to quickly recover (and sometimes strengthen) old and new results in finite geometry, including the Jamison/Brouwer-Schrijver bound on affine blocking sets. We end with a discussion of multiplicity enhancements.
rate research
Read More
Robertson and Seymour proved that every graph with sufficiently large treewidth contains a large grid minor. However, the best known bound on the treewidth that forces an $elltimesell$ grid minor is exponential in $ell$. It is unknown whether polynomial treewidth suffices. We prove a result in this direction. A emph{grid-like-minor of order} $ell$ in a graph $G$ is a set of paths in $G$ whose intersection graph is bipartite and contains a $K_{ell}$-minor. For example, the rows and columns of the $elltimesell$ grid are a grid-like-minor of order $ell+1$. We prove that polynomial treewidth forces a large grid-like-minor. In particular, every graph with treewidth at least $cell^4sqrt{logell}$ has a grid-like-minor of order $ell$. As an application of this result, we prove that the cartesian product $Gsquare K_2$ contains a $K_{ell}$-minor whenever $G$ has treewidth at least $cell^4sqrt{logell}$.
Let $A$ be an algebra and let $f(x_1,...,x_d)$ be a multilinear polynomial in noncommuting indeterminates $x_i$. We consider the problem of describing linear maps $phi:Ato A$ that preserve zeros of $f$. Under certain technical restrictions we solve the problem for general polynomials $f$ in the case where $A=M_n(F)$. We also consider quite general algebras $A$, but only for specific polynomials $f$.
In his 2006 paper, Jin proves that Kalantaris bounds on polynomial zeros, indexed by $m leq 2$ and called $L_m$ and $U_m$ respectively, become sharp as $mrightarrowinfty$. That is, given a degree $n$ polynomial $p(z)$ not vanishing at the origin and an error tolerance $epsilon > 0$, Jin proves that there exists an $m$ such that $frac{L_m}{rho_{min}} > 1-epsilon$, where $rho_{min} := min_{rho:p(rho) = 0} left|rhoright|$. In this paper we derive a formula that yields such an $m$, thereby constructively proving Jins theorem. In fact, we prove the stronger theorem that this convergence is uniform in a sense, its rate depending only on $n$ and a few other parameters. We also give experimental results that suggest an optimal m of (asymptotically) $Oleft(frac{1}{epsilon^d}right)$ for some $d ll 2$. A proof of these results would show that Jins method runs in $Oleft(frac{n}{epsilon^d}right)$ time, making it efficient for isolating polynomial zeros of high degree.
We analyze the behavior of the Euclidean algorithm applied to pairs (g,f) of univariate nonconstant polynomials over a finite field F_q of q elements when the highest-degree polynomial g is fixed. Considering all the elements f of fixed degree, we establish asymptotically optimal bounds in terms of q for the number of elements f which are relatively prime with g and for the average degree of gcd(g,f). The accuracy of our estimates is confirmed by practical experiments. We also exhibit asymptotically optimal bounds for the average-case complexity of the Euclidean algorithm applied to pairs (g,f) as above.
Let $G$ be a graph with $n$ vertices, and let $A(G)$ and $D(G)$ denote respectively the adjacency matrix and the degree matrix of $G$. Define $$ A_{alpha}(G)=alpha D(G)+(1-alpha)A(G) $$ for any real $alphain [0,1]$. The $A_{alpha}$-characteristic polynomial of $G$ is defined to be $$ det(xI_n-A_{alpha}(G))=sum_jc_{alpha j}(G)x^{n-j}, $$ where $det(*)$ denotes the determinant of $*$, and $I_n$ is the identity matrix of size $n$. The $A_{alpha}$-spectrum of $G$ consists of all roots of the $A_{alpha}$-characteristic polynomial of $G$. A graph $G$ is said to be determined by its $A_{alpha}$-spectrum if all graphs having the same $A_{alpha}$-spectrum as $G$ are isomorphic to $G$. In this paper, we first formulate the first four coefficients $c_{alpha 0}(G)$, $c_{alpha 1}(G)$, $c_{alpha 2}(G)$ and $c_{alpha 3}(G)$ of the $A_{alpha}$-characteristic polynomial of $G$. And then, we observe that $A_{alpha}$-spectra are much efficient for us to distinguish graphs, by enumerating the $A_{alpha}$-characteristic polynomials for all graphs on at most 10 vertices. To verify this observation, we characterize some graphs determined by their $A_{alpha}$-spectra.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
