اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدBinary Cyclotomic Polynomias: Representation via Words and Algorithms
130
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Cyclotomic polynomials are basic objects in Number Theory. Their properties depend on the number of distinct primes that intervene in the factorization of their order, and the binary case is thus the first nontrivial case. This paper sees the vector of coefficients of the polynomial as a word on a ternary alphabet ${-1,0 ,+1}$. It designs an efficient algorithm that computes a compact representation of this word. This algorithm is of linear time with respect to the size of the output, and, thus, optimal. This approach allows to recover known properties of coefficients of binary cyclotomic polynomials, and extends to the case of polynomials associated with numerical semi-groups of dimension 2.
قيم البحث
اقرأ أيضاً
Given a negative $D>-(log X)^{log 2-delta}$, we give a new upper bound on the number of square free integers $<X$ which are represented by some but not all forms of the genus of a primitive positive definite binary quadratic form $f$ of discriminant
$D$. We also give an analogous upper bound for square free integers of the form $q+a<X$ where $q$ is prime and $ainmathbb Z$ is fixed. Combined with the 1/2-dimensional sieve of Iwaniec, this yields a lower bound on the number of such integers $q+a<X$ represented by a binary quadratic form of discriminant $D$, where $D$ is allowed to grow with $X$ as above. An immediate consequence of this, coming from recent work of the authors in [BF], is a lower bound on the number of primes which come up as curvatures in a given primitive integer Apollonian circle packing.
Let $q$ be a power of a prime $p$, let $k$ be a nontrivial divisor of $q-1$ and write $e=(q-1)/k$. We study upper bounds for cyclotomic numbers $(a,b)$ of order $e$ over the finite field $mathbb{F}_q$. A general result of our study is that $(a,b)leq
3$ for all $a,b in mathbb{Z}$ if $p> (sqrt{14})^{k/ord_k(p)}$. More conclusive results will be obtained through separate investigation of the five types of cyclotomic numbers: $(0,0), (0,a), (a,0), (a,a)$ and $(a,b)$, where $a eq b$ and $a,b in {1,dots,e-1}$. The main idea we use is to transform equations over $mathbb{F}_q$ into equations over the field of complex numbers on which we have more information. A major tool for the improvements we obtain over known results is new upper bounds on the norm of cyclotomic integers.
In this (mostly historical) note we show how a unified Kummer-Artin-Schreier sequence from [W], [SOS] may be recovered from the relativistic velocity addition law.
Let $W^{(n)}$ be the $n$-letter word obtained by repeating a fixed word $W$, and let $R_n$ be a random $n$-letter word over the same alphabet. We show several results about the length of the longest common subsequence (LCS) between $W^{(n)}$ and $R_n
$; in particular, we show that its expectation is $gamma_W n-O(sqrt{n})$ for an efficiently-computable constant $gamma_W$. This is done by relating the problem to a new interacting particle system, which we dub frog dynamics. In this system, the particles (`frogs) hop over one another in the order given by their labels. Stripped of the labeling, the frog dynamics reduces to a variant of the PushTASEP. In the special case when all symbols of $W$ are distinct, we obtain an explicit formula for the constant $gamma_W$ and a closed-form expression for the stationary distribution of the associated frog dynamics. In addition, we propose new conjectures about the asymptotic of the LCS of a pair of random words. These conjectures are informed by computer experiments using a new heuristic algorithm to compute the LCS. Through our computations, we found periodic words that are more random-like than a random word, as measured by the LCS.
The main goal of this work is to establish a bijection between Dyck words and a family of Eulerian digraphs. We do so by providing two algorithms implementing such bijection in both directions. The connection between Dyck words and Eulerian digraphs
exploits a novel combinatorial structure: a binary matrix, we call Dyck matrix, representing the cycles of an Eulerian digraph.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
