Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA new perspective on the distance problem over prime fields
62
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $mathbb{F}_p$ be a prime field, and ${mathcal E}$ a set in $mathbb{F}_p^2$. Let $Delta({mathcal E})={||x-y||: x,y in {mathcal E} }$, the distance set of ${mathcal E}$. In this paper, we provide a quantitative connection between the distance set $Delta({mathcal E})$ and the set of rectangles determined by points in ${mathcal E}$. As a consequence, we obtain a new lower bound on the size of $Delta({mathcal E})$ when ${mathcal E}$ is not too large, improving a previous estimate due to Lund and Petridis and establishing an approach that should lead to significant further improvements.
rate research
Read More
In this paper we obtain a new lower bound on the ErdH{o}s distinct distances problem in the plane over prime fields. More precisely, we show that for any set $Asubset mathbb{F}_p^2$ with $|A|le p^{7/6}$, the number of distinct distances determined by pairs of points in $A$ satisfies $$ |Delta(A)| gg |A|^{frac{1}{2}+frac{149}{4214}}.$$ Our result gives a new lower bound of $|Delta{(A)}|$ in the range $|A|le p^{1+frac{149}{4065}}$. The main tools we employ are the energy of a set on a paraboloid due to Rudnev and Shkredov, a point-line incidence bound given by Stevens and de Zeeuw, and a lower bound on the number of distinct distances between a line and a set in $mathbb{F}_p^2$. The latter is the new feature that allows us to improve the previous bound due Stevens and de Zeeuw.
Given $E subseteq mathbb{F}_q^d times mathbb{F}_q^d$, with the finite field $mathbb{F}_q$ of order $q$ and the integer $d ge 2$, we define the two-parameter distance set as $Delta_{d, d}(E)=left{left(|x_1-y_1|, |x_2-y_2|right) : (x_1,x_2), (y_1,y_2) in E right}$. Birklbauer and Iosevich (2017) proved that if $|E| gg q^{frac{3d+1}{2}}$, then $ |Delta_{d, d}(E)| = q^2$. For the case of $d=2$, they showed that if $|E| gg q^{frac{10}{3}}$, then $ |Delta_{2, 2}(E)| gg q^2$. In this paper, we present extensions and improvements of these results.
For an integer $n>2$, a rank-$n$ matroid is called an $n$-spike if it consists of $n$ three-point lines through a common point such that, for all $kin{1, 2, ..., n - 1}$, the union of every set of $k$ of these lines has rank $k+1$. Spikes are very special and important in matroid theory. In 2003 Wu found the exact numbers of $n$-spikes over fields with 2, 3, 4, 5, 7 elements, and the asymptotic values for larger finite fields. In this paper, we prove that, for each prime number $p$, a $GF(p$) representable $n$-spike $M$ is only representable on fields with characteristic $p$ provided that $n ge 2p-1$. Moreover, $M$ is uniquely representable over $GF(p)$.
A graph $G$ is a $k$-prime product distance graph if its vertices can be labeled with distinct integers such that for any two adjacent vertices, the difference of their labels is the product of at most $k$ primes. A graph has prime product number $ppn(G)=k$ if it is a $k$-prime product graph but not a $(k-1)$-prime product graph. Similarly, $G$ is a prime $k$th-power graph (respectively, strict prime $k$th-power graph) if its vertices can be labeled with distinct integers such that for any two adjacent vertices, the difference of their labels is the $j$th power of a prime, for $j leq k$ (respectively, the $k$th power of a prime exactly). We prove that $ppn(K_n) = lceil log_2(n)rceil - 1$, and for a nonempty $k$-chromatic graph $G$, $ppn(G) = lceil log_2(k)rceil - 1$ or $ppn(G) = lceil log_2(k)rceil$. We determine $ppn(G)$ for all complete bipartite, 3-partite, and 4-partite graphs. We prove that $K_n$ is a prime $k$th-power graph if and only if $n < 7$, and we determine conditions on cycles and outerplanar graphs $G$ for which $G$ is a strict prime $k$th-power graph. We find connections between prime product and prime power distance graphs and the Twin Prime Conjecture, the Green-Tao Theorem, and Fermats Last Theorem.
The Windows Scheduling Problem, also known as the Pinwheel Problem, is to schedule periodic jobs subject to their processing frequency demands. Instances are given as a set of jobs that have to be processed infinitely often such that the time interval between two consecutive executions of the same job j is no longer than the jobs given period $p_j$. The key contribution of this work is a new interpretation of the problem variant with exact periods, where the time interval between consecutive executions must be strictly $p_j$. We show that this version is equivalent to a natural combinatorial problem we call Partial Coding. Reductions in both directions can be realized in polynomial time, so that both hardness proofs and algorithms for Partial Coding transfer to Windows Scheduling. Applying this new perspective, we obtain a number of new results regarding the computational complexity of various Windows Scheduling Problem variants. We prove that even the case of one processor and unit-length jobs does not admit a pseudo-polynomial time algorithm unless SAT can be solved by a randomized method in expected quasi-polynomial time. This result also extends to the case of inexact periods, which answers a question that has remained open for more than two decades. Furthermore, we report an error found in a hardness proof previously given for the multi-machine case without machine migration, and we show that this variant reduces to the single-machine case. Finally, we prove that even with unit-length jobs the problem is co-NP-hard when jobs are allowed to migrate between machines.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
