Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAlgorithms for Finding Almost Irreducible and Almost Primitive Trinomials
289
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Consider polynomials over ${rm GF}(2)$. We describe efficient algorithms for finding trinomials with large irreducible (and possibly primitive) factors, and give examples of trinomials having a primitive factor of degree $r$ for all Mersenne exponents $r = pm 3 bmod 8$ in the range $5 < r < 10^7$, although there is no irreducible trinomial of degree $r$. We also give trinomials with a primitive factor of degree $r = 2^k$ for $3 le k le 12$. These trinomials enable efficient representations of the finite field ${rm GF}(2^r)$. We show how trinomials with large primitive factors can be used efficiently in applications where primitive trinomials would normally be used.
rate research
Read More
In this paper we prove the existence of asymptotic moments, and an estimate on the tails of the limiting distribution, for a specific class of almost periodic functions. Then we introduce the hyperbolic circle problem, proving an estimate on the asymptotic variance of the remainder that improves a result of Chamizo. Applying the results of the first part we prove the existence of limiting distribution and asymptotic moments for three functions that are integrat
Recently, due to an increasing interest for transparency in artificial intelligence, several methods of explainable machine learning have been developed with the simultaneous goal of accuracy and interpretability by humans. In this paper, we study a recent framework of explainable clustering first suggested by Dasgupta et al.~cite{dasgupta2020explainable}. Specifically, we focus on the $k$-means and $k$-medians problems and provide nearly tight upper and lower bounds. First, we provide an $O(log k log log k)$-approximation algorithm for explainable $k$-medians, improving on the best known algorithm of $O(k)$~cite{dasgupta2020explainable} and nearly matching the known $Omega(log k)$ lower bound~cite{dasgupta2020explainable}. In addition, in low-dimensional spaces $d ll log k$, we show that our algorithm also provides an $O(d log^2 d)$-approximate solution for explainable $k$-medians. This improves over the best known bound of $O(d log k)$ for low dimensions~cite{laber2021explainable}, and is a constant for constant dimensional spaces. To complement this, we show a nearly matching $Omega(d)$ lower bound. Next, we study the $k$-means problem in this context and provide an $O(k log k)$-approximation algorithm for explainable $k$-means, improving over the $O(k^2)$ bound of Dasgupta et al. and the $O(d k log k)$ bound of cite{laber2021explainable}. To complement this we provide an almost tight $Omega(k)$ lower bound, improving over the $Omega(log k)$ lower bound of Dasgupta et al. Given an approximate solution to the classic $k$-means and $k$-medians, our algorithm for $k$-medians runs in time $O(kd log^2 k )$ and our algorithm for $k$-means runs in time $ O(k^2 d)$.
A {it two-dimensional continued fraction expansion} is a map $mu$ assigning to every $x inmathbb R^2setminusmathbb Q^2$ a sequence $mu(x)=T_0,T_1,dots$ of triangles $T_n$ with vertices $x_{ni}=(p_{ni}/d_{ni},q_{ni}/d_{ni})inmathbb Q^2, d_{ni}>0, p_{ni}, q_{ni}, d_{ni}in mathbb Z,$ $i=1,2,3$, such that begin{eqnarray*} det left(begin{matrix} p_{n1}& q_{n1} &d_{n1} p_{n2}& q_{n2} &d_{n2} p_{n3}& q_{n3} &d_{n3} end{matrix} right) = pm 1,,, ,,,mbox{and},,,,,, bigcap_n T_n = {x}. end{eqnarray*} We construct a two-dimensional continued fraction expansion $mu^*$ such that for densely many (Turing computable) points $x$ the vertices of the triangles of $mu(x)$ strongly converge to $x$. Strong convergence depends on the value of $lim_{nto infty}frac{sum_{i=1}^3dist(x,x_{ni})}{(2d_{n1}d_{n2}d_{n3})^{-1/2}},$ (dist denoting euclidean distance) which in turn depends on the smallest angle of $T_n$. Our proofs combine a classical theorem of Davenport Mahler in diophantine approximation, with the algorithmic resolution of toric singularities in the equivalent framework of regular fans and their stellar operations.
The goal of this expository article is a fairly self-contained account of some averaging processes of functions along sequences of the form $(alpha^n x)^{}_{ninmathbb{N}}$, where $alpha$ is a fixed real number with $| alpha | > 1$ and $xinmathbb{R}$ is arbitrary. Such sequences appear in a multitude of situations including the spectral theory of inflation systems in aperiodic order. Due to the connection with uniform distribution theory, the results will mostly be metric in nature, which means that they hold for Lebesgue-almost every $xinmathbb{R}$.
For each integer $x$, the $x$-th generalized pentagonal number is denoted by $P_5(x)=(3x^2-x)/2$. Given odd positive integers $a,b,c$ and non-negative integers $r,s$, we employ the theory of ternary quadratic forms to determine when the sum $aP_5(x)+2^rbP_5(y)+2^scP_5(z)$ represents all but finitely many positive integers.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
