4
$\begingroup$

In the chapter on sieve methods, specifically the $\Lambda^{2}$-sieve, Iwaniec-Kowalski state that $$\sum_{d < \sqrt{D}}^{\flat} h(d) > \prod_{p | q} (1-g(p)) \log \sqrt{D},$$ where $h(d) = \prod_{p | d} g(p)/(1-g(p))$ for $d$ squarefree and $g(p) = 1/p$ for $p \nmid q$. I tried several approaches but could not justify this inequality. Instead, I obtained a rather different lower bound.

What I did is the following: Note that each squarefree $d$ can be written uniquely as $d = u v$, where $u \mid q$, $(v,q) = 1$, and $u,v$ are squarefree. Then we have $$\sum_{d < \sqrt{D}}^{\flat} h(d) = \sum_{u | q} \mu(u)^{2}h(u)\sum_{\substack{v < \sqrt{D}/u\\ (v,q) = 1}}^{\flat} \frac{1}{\varphi(v)} = \sum_{\substack{v < \sqrt{D}\\(v,q) = 1}}^{\flat}\frac{1}{\varphi(v)} \sum_{\substack{u | q\\u < \sqrt{D}/v}} \mu^{2}(u) h(u).$$ Next, restrict to $v < \sqrt{D}/q$, so that $q < \sqrt{D}/v$ and hence the condition $u < \sqrt{D}/v$ is satisfied for all $u \mid q$. The inner sum then becomes a clean convolution, which simplifies to $\prod_{p | q} (1-g(p))^{-1}$. Thus, we conclude $$\ge \prod_{p | q} (1-g(p))^{-1}\sum_{\substack{v < \sqrt{D}/q\\(v,q) = 1}}^{\flat}\frac{1}{\varphi(v)} > \prod_{p | q} (1-g(p))^{-1}\frac{\varphi(q)}{q}\log \sqrt{D}/q.$$ This seems to be the strongest bound I can obtain, assuming there are no mistakes above. Does anyone know how to recover the bound stated in the book?

$\endgroup$
4
  • $\begingroup$ How exactly is $g$ defined? What value does $g(p)$ take when $p|q$? $\endgroup$ Commented Sep 10 at 16:56
  • $\begingroup$ @SayanDutta $g$ is supported on the squarefree integers and satisfies $0\le g(p)<1$ for each prime $p$. When $p\nmid q$ we assume $g(p)=1/p$, so those primes contribute the clean factor $1/\varphi(v)$. For the primes dividing $q$, we leave them unspecified. $\endgroup$ Commented Sep 10 at 17:53
  • $\begingroup$ I should also note here that I strongly suspect this bound is a mistake on their part, since IK has many such errors, but I cannot think of a counterexample. I have not had much time to try to construct one, though I believe one exists. $\endgroup$ Commented Sep 10 at 17:58
  • $\begingroup$ I believe a multiplicative $$g(p)=\begin{cases} 1/p, & p\neq 3,\\[4pt] 0, & p=3. \end{cases}$$ should work for a counterexample. Taking a big $D$ (like $50^2$) and computing the LHS and RHS will probably give a contradiction. $\endgroup$ Commented Sep 10 at 19:30

1 Answer 1

1
$\begingroup$

As mentioned in the comments, consider a multiplicative function $$g(p)=\begin{cases} 1/p, & p\neq 3,\\[4pt] 0, & p=3. \end{cases}$$ and take $D=1000^2$.

limit = 1000  # sqrt(D)

rows_large = []
sum_exact_large = Fraction(0, 1)

for d in range(1, limit):
    if math.gcd(d, q) != 1:
        continue
    if not is_squarefree(d):
        continue
    pf = prime_factors(d)
    h_frac = Fraction(1, 1)
    for p in pf:
        gp = g_value(p)
        h_frac *= gp / (1 - gp)
    rows_large.append((d, pf if pf else [1], h_frac))
    sum_exact_large += h_frac

sum_fraction_large = sum_exact_large
sum_decimal_large = Decimal(sum_fraction_large.numerator) / Decimal(sum_fraction_large.denominator)

log1000 = Decimal(math.log(1000))
diff_large = sum_decimal_large - log1000

print("Exact sum as Fraction:", sum_fraction_large)
print("Exact sum as decimal  :", sum_decimal_large)
print("log(1000) decimal     :", log1000)
print("Difference (sum - log1000):", diff_large)

The code was given by chatGPT and it yields

Exact sum as Fraction: 163286162667302329551853737294986374525397406728815214116802581120421468696193585790993804737718017737/28460629209583145330843126527256226769371639375469716512732596490367286638268217400936567466377432000
Exact sum as decimal : 5.7372646776312762735618078523879457940425078063734
log(1000) decimal : 6.907755278982136815102421678602695465087890625
Difference (sum - log1000): -1.1704906013508605415406138262147496710453828186266
$\endgroup$
1
  • $\begingroup$ Awesome! Thank you. $\endgroup$ Commented Sep 11 at 21:59

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.