Multi-target hyperbolic sieves and elliptic trace obstructions

Abstract

Let $N=pq$ be a semiprime and let $\ell \nmid Na$ be an odd prime. The hyperbolic sieve set $H_a(N;\ell )=\{ax+N{x}^{-1}:x\in {\mathbb{F}}_{\ell }^{\ast }\}$ contains the residue of the linear form $ap+q$ modulo $\ell$ and has exact cardinality $(\ell +\ddot{I}‡(aN))/2$, where $\ddot{I}‡$ is the Legendre symbol modulo $\ell$. We study simultaneous sieving for several linear forms and give a complete local analysis of the two-target primitive-root case proposed in connection with deterministic integer factorization. For two distinct coefficients $a,b$, with $A=4aN$ and $B=4bN$, we prove an exact formula for $|H_a(N;\ell )\cup H_b(N;\ell )|$ in terms of the degree-four character sum \[ K(A,B)=\sum_{z\in\mathbb F_\ell}χ((z^2-A)(z^2-B)).\] For a smooth projective genus-one curve $E/{\mathbb{F}}_{\ell }$, we write $t_E=\ell +1-\#E({\mathbb{F}}_{\ell })$ for its Frobenius trace. With this convention, $K(A,B)$ is the Frobenius trace, up to sign and an additive constant, of the genus-one curve $Y^2=(X^2-A)(X^2-B)$. Hence Hasse--Weil gives a uniform $O(\sqrt{\ell })$ error from the main term $3\ell /4$, and negative traces explain the counterexamples to the pointwise bound $3\ell /4+1$. We also prove a multi-target estimate \[\left|\left|\bigcup_{j=1}^k H_{a_j}(N;\ell)\right|-\ell(1-2^{-k})\right|\le (k-1+2^{-k})\sqrt\ell+k\] for distinct coefficients $a_1,\dots ,a_k$, together with the corresponding CRT product bound. Finally, for special-shape inputs $N=u^{r}v$, we study the $r$-power-constrained image $H_{a,r}(N;\ell )$ and determine its exact size by an elementary involution argument. These results recast the proposed local sieve questions as explicit finite-field statements with verified local tests.

23 pages