The Weighted Davenport Constant of a Group and a Related Extremal Problem

TL;DR

The paper introduces the weighted Davenport constant \(D_A(G)\) and the extremal function \(f^{(D)}_G(k)=\min\{|A|:D_A(G)\le k\}\), studying when this parameter is finite and bounding it. For cyclic groups of prime order it obtains near-optimal bounds for all \(k\) for sufficiently large primes, with asymptotically tight (up to constants) results for \(k=2\) and \(k=4\).

Key findings

• For \(G=\mathbb Z_p\), \(p\) prime, Theorem 1 gives near-optimal bounds on \(f^{(D)}(p,k)\) for all \(k\ge2\) and sufficiently large \(p\). Theorem 6 shows that for a \(\theta\)-random \(A\subseteq[1,p-1]\), if \(\theta>(\sqrt{2\log p}+\omega(p))/p\) then \(D_A(\mathbb Z_p)=2\) whp; and for \(k\ge3\), if \((p\log p)^{1/k}/p\ll\theta\ll p^{1/(k-1)}/p\), then \(D_A(\mathbb Z_p)=k\) whp.
• Theorem 2: for odd prime \(p\), if \(p=q^2+q+1\) for some prime \(q\), then \(f^{(D)}(p,2)=\lceil\sqrt p-1\rceil\); always \(f^{(D)}(p,2)\le2\lceil\sqrt p\rceil\); and \(f^{(D)}(p,4)\le C_0p^{1/4}\) for some constant \(C_0>0\). Thus \(f^{(D)}(p,k)\) is of order \(p^{1/k}\) for \(k=2,4\) up to a constant factor.
• For \(G=\mathbb Z_{p^m}\), \(f^{(D)}_G(k)=f^{(D)}(p,k)\). Proposition 3.3 gives \(f^{(D)}(n,k)\le2(n^{1/(k-1)}-1)\), and for \(G=\mathbb Z_{n_1}\times\cdots\times\mathbb Z_{n_s}\), \(f^{(D)}_G(k)\le2(|G|^{1/(k-s-1)}-1)\) for \(s>1\).
• Proposition 4.1: if \(A\) is a \(\theta\)-random subset of \([1,n-1]\) with \(\theta\ge\omega(n)/\sqrt n\), then \(D_A(G)\le\lfloor\log_2|G|\rfloor+1\) whp; hence for \(k\le\lfloor\log_2|G|\rfloor+1\), \(f^{(D)}_G(k)\le O(\sqrt n\log n)\). For the dual problem, for \(p\) prime and \(|A|=k\), the maximum \(D_A(\mathbb Z_p)\) is at most \(\lceil p/k\rceil\), with equality for \(A=\{1,\dots,k\}\).

Methods

• Theoretical additive-combinatorics/zero-sum study: defines \(D_A(G)\) and \(f^{(D)}_G(k)\), then proves finiteness and upper/lower bounds for finite abelian groups and prime cyclic groups.
• Main tools include the probabilistic method with \(\theta\)-random subsets and Janson’s inequality, difference sets and Singer’s theorem for the \(k=2\) tight case, generalized arithmetic progressions and hypergraph intersection arguments for \(k=4\), and the Combinatorial Nullstellensatz for the dual problem.
• No empirical data or sample; the objects are finite abelian groups, group sequences, primes, and subsets of integers.

Limitations

• Stated: Theorem 6 is not tight; the constant \(3\) in its statement is not tight; the authors make no attempt to optimize \(C_0\); they believe \(f^{(D)}(p,k)=\Theta(p^{1/k})\) and even \(f^{(D)}(p,k)\le(1+o(1))p^{1/k}\), but can prove neither statement; the best upper bound for \(f^{(D)}(p,2)\) for all prime \(p\) is \((2/\sqrt3)\sqrt p=1.154\ldots\sqrt p\).
• Stated/evident: the main \(\mathbb Z_p\) bounds require sufficiently large primes \(p>p_0(k)\) and are asymptotic; the exact tightness for \(k=2\) when \(p=q^2+q+1\) depends on the Hardy–Littlewood conjecture that infinitely many such prime pairs exist.
• Evident: the paper’s general \(\Theta(p^{1/k})\) picture remains conjectural, and several constants in the proofs are explicitly not optimized.