Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDiscrepancy in modular arithmetic progressions
224
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Celebrated theorems of Roth and of Matouv{s}ek and Spencer together show that the discrepancy of arithmetic progressions in the first $n$ positive integers is $Theta(n^{1/4})$. We study the analogous problem in the $mathbb{Z}_n$ setting. We asymptotically determine the logarithm of the discrepancy of arithmetic progressions in $mathbb{Z}_n$ for all positive integer $n$. We further determine up to a constant factor the discrepancy of arithmetic progressions in $mathbb{Z}_n$ for many $n$. For example, if $n=p^k$ is a prime power, then the discrepancy of arithmetic progressions in $mathbb{Z}_n$ is $Theta(n^{1/3+r_k/(6k)})$, where $r_k in {0,1,2}$ is the remainder when $k$ is divided by $3$. This solves a problem of Hebbinghaus and Srivastav.
rate research
Read More
Let the random variable $X, :=, e(mathcal{H}[B])$ count the number of edges of a hypergraph $mathcal{H}$ induced by a random $m$ element subset $B$ of its vertex set. Focussing on the case that $mathcal{H}$ satisfies some regularity condition we prove bounds on the probability that $X$ is far from its mean. It is possible to apply these results to discrete structures such as the set of $k$-term arithmetic progressions in the cyclic group $mathbb{Z}_N$. Furthermore, we show that our main theorem is essentially best possible and we deduce results for the case $Bsim B_p$ is generated by including each vertex independently with probability $p$.
In this paper, we investigate the anti-Ramsey (more precisely, anti-van der Waerden) properties of arithmetic progressions. For positive integers $n$ and $k$, the expression $aw([n],k)$ denotes the smallest number of colors with which the integers ${1,ldots,n}$ can be colored and still guarantee there is a rainbow arithmetic progression of length $k$. We establish that $aw([n],3)=Theta(log n)$ and $aw([n],k)=n^{1-o(1)}$ for $kgeq 4$. For positive integers $n$ and $k$, the expression $aw(Z_n,k)$ denotes the smallest number of colors with which elements of the cyclic group of order $n$ can be colored and still guarantee there is a rainbow arithmetic progression of length $k$. In this setting, arithmetic progressions can wrap around, and $aw(Z_n,3)$ behaves quite differently from $aw([n],3)$, depending on the divisibility of $n$. As shown in [Jungic et al., textit{Combin. Probab. Comput.}, 2003], $aw(Z_{2^m},3) = 3$ for any positive integer $m$. We establish that $aw(Z_n,3)$ can be computed from knowledge of $aw(Z_p,3)$ for all of the prime factors $p$ of $n$. However, for $kgeq 4$, the behavior is similar to the previous case, that is, $aw(Z_n,k)=n^{1-o(1)}$.
In this note we are interested in the problem of whether or not every increasing sequence of positive integers $x_1x_2x_3...$ with bounded gaps must contain a double 3-term arithmetic progression, i.e., three terms $x_i$, $x_j$, and $x_k$ such that $i + k = 2j$ and $x_i + x_k = 2x_j$. We consider a few variations of the problem, discuss some related properties of double arithmetic progressions, and present several results obtained by using RamseyScript, a high-level scripting language.
We present results on the existence of long arithmetic progressions in the Thue-Morse word and in a class of generalised Thue-Morse words. Our arguments are inspired by van der Waerdens proof for the existence of arbitrary long monochromatic arithmetic progressions in any finite colouring of the (positive) integers.
Dirichlets proof of infinitely many primes in arithmetic progressions was published in 1837, introduced L-series for the first time, and it is said to have started rigorous analytic number theory. Dirichlet uses Eulers earlier work on the zeta function and the distribution of primes. He first proves a simpler case before going to full generality. The paper was translated from German by R. Stephan and given a reference section.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
