A closed rectifiable curve on the torus Td=Rd/Zd is a t-design curve if normalized arclength integration is exact for trigonometric polynomials e2πi⟨m,x⟩ with frequencies m∈Zd satisfying ∥m∥∞≤t. For the arclength L of such curves, we establish the sharp lower bound \begin{equation}\label{eq:abs} L\geq \Big(\frac{(t+1)^{2d}-1}{t(t+2)}\Big)^{1/2}. \end{equation} Equality is attained by the family of Korobov curves described in \cite{Kunis,Lindblad}. For even t, we also derive an explicit lower bound on the length of total-degree t-design curves, defined by the frequency condition ∥m∥1≤t. This bound is sharp for t=2 in every dimension and for every even t in dimension two. We determine the minimum length of hyperbolic cross t2-design curves in dimension two. For d≥3, we establish lower bounds of optimal order for the length of hyperbolic cross td-design curves. Finally, we obtain lower bounds of optimal order for the length of t-design curves associated with sparse frequency sets.
Introduction
Exact integration along closed curves was used in [4] to approximate measures on the torus and the sphere, with exactness imposed on trigonometric polynomials and spherical polynomials, respectively. The notion of a t-design curve was subsequently introduced on the sphere in [5], requiring normalized arclength integration to be exact for all spherical polynomials of degree at most t. Such curves are analogues of spherical t-design point sets [2], which have been studied extensively for several decades [1]. More recently, asymptotically optimal t-design curves were constructed by Lindblad [11] on S3⊆R4 and on tori, and by Kunis [10] on tori. King and Mixon [9] obtained explicit spectral lower bounds on the length and exact optimality results for 2-design curves on odd-dimensional spheres S2d−1⊆R2d.
We concentrate on the torus Td=Rd/Zd.
Definition 1.1. Let t be a positive integer. A rectifiable curve γ:[0,L]→Rd with γ(L)−γ(0)∈Zd, parametrized by arclength, is called a t-design curve on Td if
Key words and phrases.t-designs, curves, torus, trigonometric polynomials.
Kunis [10] obtained explicit lower bounds on the length needed for exact trigonometric quadrature as in (1). The bounds are of optimal order in t and allow additional weighting in the arclength integral, hence, hold for a larger class than t-design curves. For even t, a simplified version in [10 Theorem 3.10] gives L≥2d+10.94(t+1)d−1. Here, in the stricter unweighted setting of t-design curves, we derive the estimate (1) that implies L≥(t+1)d−1. This bound turns out to be sharp.
We adapt King and Mixon’s spectral approach on the sphere [9] to the torus:
(a) The design property makes a suitable family of exponential functions along the curve orthonormal.
(b) Fourier analysis and Bessel’s inequality yield a lower bound for the averaged L2-energy of derivatives of this family.
(c) On the torus, the energy and the lower bound can be evaluated explicitly.
We derive results for four frequency shapes:
(1) t-design curve. The resulting estimate (1) is sharp. The Korobov curves described in [10, 11] attain this bound and therefore have minimum length among all t-design curves on Td. These main results are derived in § 2.
(2) Total degree t-design curve. We also consider the related notion of total-degree t-design curves in § 3, where the frequencies are {m∈Zd:∥m∥1≤t}. Curves of minimal length are constructed for total-degree 1 and 2 in every dimension and for every even total degree in dimension two.
(3) Hyperbolic cross t-design curves. We discuss the hyperbolic cross [3, 8],
Hd(t):={m∈Zd:j=1∏dmax(1,∣mj∣)≤t},
as an alternative to tensor-product frequency sets in § 4. We derive sharp bounds for exact arclength integration of frequencies in the hyperbolic cross in dimension d=2. For d≥3, we obtain sharp lower bounds on the order of the length. This higher-dimensional hyperbolic-cross bound is attained by a construction that uses a uniform lattice-point counting argument and a hyperbolic-cross estimate.
(4) Sparse t-design curves. Finally, we consider the sparse frequency sets
Ωd,r(t)={m∈Zd:∥m∥∞≤t,#supp(m)≤r},1≤r≤d.
The corresponding trigonometric polynomials are sums of terms depending on at most r coordinates. For fixed d and r, we establish lower bounds of order tr−1 for the length of design curves associated with these frequencies and verify the existence of simple closed geodesics with matching length order. Thus the optimal length exponent is determined by the sparsity parameter r, rather than by the ambient dimension d.
Sharp length bounds for t-design curves
Let d be a positive integer and denote the d-dimensional torus by Td=Rd/Zd, endowed with the normalized Haar measure dx. We write ds for the Lebesgue measure on the real line. A closed rectifiable curve on Td of length L>0 is represented by a path γ:[0,L]→Rd, parametrized by arclength, satisfying
γ(L)−γ(0)∈Zd.
The corresponding closed curve on Td is obtained by reduction modulo Zd. The uniform condition ∥m∥∞≤t follows the exact integration conditions used in [10]. Since the Fourier basis is orthonormal and the integral on the right-hand side of (1) is the inner product with the constant 1, we have ∫Tde2πi⟨m,x⟩dx=δm,0.
Theorem 2.1.Suppose t is a positive integer. If γ is a t-design curve on Td of length L, then
L≥(t(t+2)(t+1)2d−1)1/2(2)
There are t-design curves on Td that attain this bound.
The t-design curves attaining this bound appeared in [10, 11], and we refer to them as Korobov curves. Let d and t be positive integers, and define the Korobov vector
vd,t:=(1,t+1,…,(t+1)d−1)T∈Zd.(3)
The associated curve γd,t:[0,1]→Rd, γd,t(s)=svd,t parametrizes the line segment from the origin to vd,t. Its length is
L=∥vd,t∥2=(t(t+2)(t+1)2d−1)1/2.(4)
The arclength parametrization is γd,t:[0,L]→Rd, s↦∥vd,t∥2svd,t, so that γd,t(L)−γd,t(0)=vd,t∈Zd. It was mentioned in [11] and verified in [10] that they form t-design curves. Thus, (3) is sharp.
The proof of the lower bound (3) in Theorem 2.1 needs some preparation. Let γ:[0,L]→Rd be a rectifiable curve, parametrized by arclength. For every a∈Rd, define a function fa:[0,L]→C,
fa(s):=e2πi⟨a,γ(s)⟩.
We restrict a to a suitable cube of side length t centered at 0. For every positive integer t, the set
[t]:={0,1,…,t}−t/2
has cardinality t+1, and the Cartesian product [t]d has (t+1)d elements. If t is even, then [t]d⊆Zd, and t odd yields [t]d⊆(Z+21)d. The difference satisfies [t]d−[t]d⊆[−t,t]d∩Zd, no matter if t is even or odd.
Invariance of [t]d under coordinate sign changes and permutations implies that the covariance matrix of the product lattice [t]d is a scalar multiple of the identity Id. Further direct calculation for the discrete uniform distribution as in [7 Section 2.3.3] shows
(t+1)d1a∈[t]d∑aaT=12t(t+2)Id.(5)
This isotropy property is key to the following lemma.
Lemma 2.2. Suppose t is a positive integer and let γ:[0,L]→Rd be a rectifiable curve, parametrized by arclength. Then fa′∈L2([0,L],ds/L), for all a∈[t]d, and
The identity (7) in Lemma 2.2 holds independently of the design property but relies on the isotropy condition (6).
Proof of Lemma 2.2. Since γ is rectifiable and parametrized by arclength, it is 1-Lipschitz. Consequently, fa is Lipschitz as well. Therefore, both are differentiable almost everywhere with
∥γ′∥2=1,fa′=2πi⟨a,γ′⟩fa.(7)
This also implies almost everywhere
∣fa′∣2=4π2∣⟨a,γ′⟩∣2=4π2γ′TaaTγ′.(8)
We have ∥fa∥L∞([0,L])=1 and ∥fa′∥L∞([0,L])≤2π∥a∥2, so that, in particular, fa′∈L2([0,L],ds/L).
To complete the proof of Theorem 2.1, we verify Proposition 2.4.
Proof of Proposition 2.4. Let N=#[t]d and v=γ(L)−γ(0)∈Zd. The parity of t and v1+⋯+vd lead to three cases.
(i) We first treat the case when t is even, so that [t]d⊆Zd. For each a∈[t]d, the function fa satisfies fa(L)=fa(0), and we denote its Fourier coefficients by
ck(fa)=L1∫0Lfa(s)e−2πiks/Lds,k∈Z.
Since fa is Lipschitz continuous, it is absolutely continuous and the Fourier coefficients of fa′ are determined by the standard relation
ck(fa′)=L2πikck(fa),k∈Z.(10)
Parseval’s identity turns the L2-norm of fa′ into a weighted sequence norm of Fourier coefficients of fa,
so that (12) with N=(t+1)d leads to the claimed estimate (10) in Proposition 2.4.
(ii) Let t be odd and suppose that v=γ(L)−γ(0) is such that v1+⋯+vd is even. For a∈[t]d⊂(Z+21)d, this still implies ⟨a,v⟩∈Z, as when t is even. Hence,
fa(L)=e2πi⟨a,γ(L)⟩=e2πi⟨a,v+γ(0)⟩=fa(0).
Thus, the functions fa still satisfy (11), and we can follow the case (i) using the standard Fourier coefficients. Since t is odd, N is even, and M:=N/2 is an integer. To keep sums of length N, we switch from ∑∣k∣≤M to ∑k=−MM−1. Computations analogous to the case (i) lead to
This gives a slightly stronger bound in this case.
(iii) For t odd and v1+⋯+vd odd, we have ⟨a,v⟩∈Z+21 for all a∈[t]d, hence, the functions fa satisfy
fa(L)=−fa(0).
Thus, the derivative relation (11) for Fourier coefficients no longer holds with the standard Fourier basis, and we must change to an anti-periodic basis. We use
ϕk(s)=e2πi(k+21)s/L,k∈Z.
This is an orthonormal basis for L2([0,L],ds/L), and the half-integer Fourier coefficients of fa are
ck+21(fa):=L1∫0Lfa(s)e−2πi(k+21)s/Lds,k∈Z.
Since fa(L)=−fa(0) and e−2πi(k+21)=−1, the boundary term in integration by parts vanishes, and hence
Remark 2.5. Case (ii) in the proof of Proposition 2.4 yields a stronger bound under an additional parity assumption. If γ is a t-design curve on Td of length L, t is odd, and v1+⋯+vd is even for v=γ(L)−γ(0), then L≥(t(t+2)(t+1)2d+2)1/2.
Total-degree t-design curves
Definition 1.1 addressed the uniform frequency range ∥m∥∞≤t. Design curves are considered in [11] for trigonometric polynomials of total degree at most t, corresponding to the frequency condition ∥m∥1≤t.
Definition 3.1.Let t be a positive integer. A rectifiable curve γ:[0,L]→Rd with γ(L)−γ(0)∈Zd, parametrized by arclength, is called a total-degree t-design curve on Td if
L1∫0Le2πi⟨m,γ(s)⟩ds=∫Tde2πi⟨m,x⟩dx,(12)
for every m∈Zd satisfying ∥m∥1≤t.
Every t-design curve in the sense of Definition 1.1 is also a total-degree t-design curve, because ∥m∥1≤t implies ∥m∥∞≤t.
The curve γd,t induced by the Korobov vector (3) is a total-degree (t+1)-design curve. The latter is seen as follows. For 0<∥m∥1≤t+1, either ∥m∥∞≤t, in which case exactness follows from the Korobov curve being a t-design, or there is mi=±(t+1), in which case ⟨m,vd,t⟩=0.
Total-degree one
We proceed by first determining the minimum length for total-degree 1-design curves. For even degrees, we then derive a general lower bound and show that it is attained for t=2 in every dimension and for every even t in dimension two.
Lemma 3.2. The curve γ:[0,d]→Rd, s↦ds(1,…,1)⊤ is a total-degree 1-design curve. Its length d is minimal among all total-degree 1-design curves on Td.
Proof. The design property follows from the observation that every nonzero m∈Zd with ∥m∥1≤1 satisfies ⟨m,(1,…,1)⊤⟩=0.
To prove the lower bound on the length, we again follow the approach of [9], which takes a particularly simple form in this case. Let γ:[0,L]→Rd be a total-degree 1-design curve. For j=1,…,d, define fj:=fej, so that
fj(s)=e2πi⟨ej,γ(s)⟩=e2πiγj(s),0≤s≤L.
According to ∣fj′∣2=4π2∣γj′∣2 and 1=∥γ′∥22=∑j=1d∣γj′∣2 almost everywhere we obtain
d1j=1∑dL1∫0L∣fj′(s)∣2ds=d4π2.
Since ∣fj(s)∣=1, the functions fj have unit norm, L1∫0L∣fj(s)∣2ds=1. The design property does not imply orthonormality of f1,…,fd, but they are orthogonal to the constant function, L1∫0Lfj(s)ds=0. A Fourier coefficient argument using (10) leads to
L1∫0L∣fj′(s)∣2ds≥(L2π)2.
Thus, we obtain d4π2≥(L2π)2, which yields L≥d. □
Even total-degree
Assume t=2n is even. Set
Ad,n:={a∈Zd:∥a∥1≤n},Nd,n:=#Ad,n.
This yields Ad,n−Ad,n⊆{m∈Zd:∥m∥1≤t}, and the quantity
σd,n:=Nd,n1a∈Ad,n∑aj2,j=1,…,d,
is independent of j. Invariance of Ad,n under coordinate sign changes and permutations implies
Nd,n1a∈Ad,n∑aa⊤=σd,nId,
that leads to a lower bound on the length of total-degree t-design curves.
Theorem 3.3. Suppose t=2n is a positive even integer. If γ is a total-degree t-design curve on Td of length L, then
L≥(12σd,nNd,n2−1)1/2.(13)
Proof. We repeat the argument of Section 2 with the functions fa(s)=e2πi⟨a,γ(s)⟩ but the centered cube [t]d replaced by Ad,n. The isotropy condition allows the computation of
Nd,n1a∈Ad,n∑L1∫0L∣fa′(s)∣2ds=4π2σd,n,
and the total-degree t-design property (13) ensures that the functions {fa:a∈Ad,n} are orthonormal in L2([0,L],ds/L).
The set Ad,n consists of the origin and pairs {a,−a}, so that Nd,n is odd, and we may follow case (i) in the proof of Proposition 2.4. It leads to
where we use the convention N0,p=Nq,0=1 for p,q≥0.
For r≥1, the number of triplets (a1,a2,a3)∈Z3 satisfying ∣a1∣+∣a2∣+∣a3∣=r can be counted by adding the numbers for exactly one, two, or three nonzero coordinates
and is 6+12(r−1)+8(2r−1)=4r2+2. According to the sum r of the absolute values of their last three coordinates, we obtain
Nd+2,n=Nd−1,n+r=1∑n(4r2+2)Nd−1,n−r.
Similarly, we determine
Nd,n=Nd−1,n+2r=1∑nNd−1,n−r.
Subtracting one from the other yields
Nd+2,n−Nd,n=4r=1∑nr2Nd−1,n−r=2Nd,nσd,n,
so that σd,n=21(Nd,nNd+2,n−1). The observation Nd,n∼2dnd/d! implies σd,n∼(d+1)(d+2)2n2 and combining both gives (15).
Minimal length for d=2 or t=2
We specify Theorem 3.3 for two distinct cases.
Corollary 3.5. Suppose n≥1 is an integer.
(d=2) If γ is a total-degree 2n-design curve on T2 of length L, then
L≥2n2+2n+1.(15)
(t=2) If γ is a total-degree 2-design curve on Td of length L, then
L≥61d(d+1)(2d+1).(16)
We will see that there are curves that attain these bounds.
Proof. (a) For d=2, we have N2,n=2n2+2n+1 and N4,n−N2,n=32n(n+1)(n2+n+1). We can calculate σ2,n by
Since N2,n2−1=4n(n+1)(n2+n+1), substitution into (14) gives L2≥12σ2,nN2,n2−1=2n2+2n+1.
(b) For t=2, the Delannoy numbers simplify to Nd,1=2d+1, and we obtain σd,1=2/(2d+1), so that 12σd,1Nd,12−1=61d(d+1)(2d+1).
Example 3.6. Let t=2. The curve associated to the vector
wd=(1,2,…,d)T
is a total-degree 2-design curve on Td. Indeed, if m has one nonzero entry, then ⟨m,wd⟩=0. If it has two nonzero entries, both have modulus one, and the corresponding entries of wd are positive and distinct, giving ⟨m,wd⟩=0. Its length is Ld=61d(d+1)(2d+1), which is minimal among all total-degree 2-design curves on Td by Corollary 3.5.
The following construction provides total-degree 2n-design curves in every dimension and attains the bound (16) of Corollary 3.5 when d=2. Let t be a positive even integer, so that t=2n. The curve associated to the vector
wd,n=(nd−1,nd−2(n+1),…,(n+1)d−1)T
is βd,n(s)=∥wd,n∥2swd,n, for 0≤s≤∥wd,n∥2=Ld,n.
Lemma 3.7. The curve βd,n is a total-degree 2n-design curve on Td of length
Ld,n=(2n+1(n+1)2d−n2d)1/2.
For large n, the asymptotic is Ld,n∼dnd−1.
Proof. Suppose ⟨m,wd,n⟩=0 for some nonzero m∈Zd. Since every entry of wd,n is positive, m has at least two nonzero entries. Let r<s be their first and last indices. Dividing the relation by nd−s(n+1)r−1 gives
j=r∑smjns−j(n+1)j−r=0.
Every term with j>r contains a factor n+1. Since the sum is zero, n+1 must also divide the first term mrns−r. As n and n+1 are coprime, this gives (n+1)∣mr. Similarly, every term with j<s contains a factor n, so n divides the last term ms(n+1)s−r, and hence n∣ms. Both entries are nonzero, so
∥m∥1≥∣mr∣+∣ms∣≥2n+1.
Thus, whenever 0<∥m∥1≤2n, the integer ⟨m,wd,n⟩ is nonzero. It follows that βd,n is a total-degree 2n-design curve on Td.
To compute the length Ld,n=∥wd,n∥2, we recall the standard identity
Example 3.8. For d=2 and n a positive integer, β2,n is a total-degree 2n-design curve on T2 with w2,n=(n,n+1)T and length L2,n=2n2+2n+1. The length is minimal among all total-degree 2n-design curves on T2 by Corollary 3.5.
Examples 3.6 and 3.8 show that the bounds in Corollary 3.5 are sharp.
Hyperbolic cross design curves
Hyperbolic crosses provide a standard alternative to tensor-product frequency sets [3, 8]. We denote the d-dimensional hyperbolic cross by
Hd(t):={m∈Zd:j=1∏dmax(1,∣mj∣)≤t}.
and define design curves for frequencies in Hd(t).
Definition 4.1. Let t be a positive integer. A rectifiable curve γ:[0,L]→Rd with γ(L)−γ(0)∈Zd, parametrized by arclength, is called a hyperbolic cross t-design curve on Td if
L1∫0Le2πi⟨m,γ(s)⟩ds=∫Tde2πi⟨m,x⟩dx,
for every m∈Hd(t).
Sharp bounds for d=2
For the hyperbolic cross in dimension two, we obtain a sharp lower bound on the length of such design curves.
Theorem 4.2. Let n≥1 be an integer and d=2.
(a) If γ is a hyperbolic cross n2-design curve on T2, then its length L satisfies
L≥2n2+2n+1.
(b) The curve β2,n in Example 3.8 is a hyperbolic cross n2-design and attains this bound.
It is a feature of the hyperbolic cross that the design strength can be n2 although the length is only of order n.
Proof. (a) Suppose first that n≥2. Consider m∈Z2 such that ∥m∥1≤2n. If both coordinates are nonzero, then ∣m1m2∣≤(∥m∥1/2)2≤n2. Otherwise we have
max{1,∣m1∣}max{1,∣m2∣}≤2n≤n2.
Consequently,
{m∈Z2:∥m∥1≤2n}⊆H2(n2),
and every hyperbolic cross n2-design curve on T2 is also a total-degree 2n-design curve. Corollary 3.5 therefore yields L≥2n2+2n+1.
For n=1, the hyperbolic cross is H2(1)={−1,0,1}2, so γ is a 1-design curve in the sense of Definition 1.1. Theorem 2.1 gives L≥(324−1)1/2=5, which is the claimed bound for n=1.
(b) The curve in Example 3.8 is β2,n(s)=L2,nsw2,n with w2,n=(n,n+1)T and its length L2,n=2n2+2n+1 matches the bound in Part (a). To verify the design property, it is sufficient to check that
⟨m,w2,n⟩=0for every m∈H2(n2)∖{0}.
Indeed, if m=0 and nm1+(n+1)m2=0, then (n+1)m2=−nm1. Since n and n+1 are coprime, n+1 must divide m1, so that there is k∈Z∖{0} such that k(n+1)=m1. Thus, we obtain
0=nk(n+1)+(n+1)m2=(n+1)(nk+m2),
so that m2=−nk. This also implies m=k(n+1,−n)T. Consequently,
max{1,∣m1∣}max{1,∣m2∣}=k2n(n+1)≥n(n+1)>n2,
which leads to m∈/H2(n2).
Thus, for every nonzero m∈H2(n2), the integer ⟨m,w2,n⟩ is nonzero, and this implies exact integration of e2πi⟨m,x⟩. For m=0, the normalized integral equals 1. Hence β2,n is a hyperbolic cross n2-design curve. □
Sharp asymptotic bounds for d≥3
We determine a sharp asymptotic bound on the length when the dimension is bigger than two.
Theorem 4.3. Let d≥3 be an integer.
(a) If γ is a hyperbolic cross nd-design curve on Td, for some positive integer n, then its length L satisfies
L≥nd−1.
(b) There is a constant Cd>0 such that, for all positive integers n, there exists a simple, hyperbolic cross nd-design curve on Td of length L≤Cdnd−1.
Before we can prove this theorem, we need to verify some estimates regarding the hyperbolic cross.
Lemma 4.4. Let n≥1 be an integer.
(i) For all integers d≥2,
m∈Hd(nd)∖{0}∑∥m∥∞1≤d−1(3d)dnd−1.(17)
(ii) For all integers d≥3, there is a constant cd>0 such that
#Hd(nd)≤cdn2(d−1).(18)
Proof of Lemma 4.4. (i) Let N=nd. For m∈Hd(N)∖{0}, the substitution aj=max(1,∣mj∣) has at most 3d preimages and satisfies ∥a∥∞=∥m∥∞, so that we derive
Except on a set of measure zero, every x has a unique largest coordinate. Thus we can split the integration domain into d regions, according to which coordinate is largest. By symmetry, we may take xd=r as the largest coordinate and write xj=ryj, with 0<yj<1, for j<d. According to dx=rd−1dydr and xd=r, we obtain
(ii) All implicit constants1 below depend only on d. According to [3], we note that
#Hd(N)≲dN(1+logN)d−1
provided that N≥1 and d≥3. Since (1+logN)d−1≲dN(d−2)/d, we obtain
#Hd(N)≲dN1+(d−2)/d=N2(d−1)/d.
Proof of Theorem 4.3. (a) We observe that [−n,n]d∩Zd⊆Hd(nd), so that Theorem 2.1 yields
L2≥n(n+2)(n+1)2d−1=j=0∑d−1(n+1)2j≥(n+1)2(d−1).
This implies L≥(n+1)d−1≥nd−1.
(b) We aim to find v∈Zd such that ∥v∥2≤Cdnd−1 and ⟨v,m⟩=0, for all m∈Hd(nd)∖{0}. Then the straight line s↦∥v∥2sv constitutes the hyperbolic cross nd-design curve.
We say that m∈Zd∖{0} is primitive if its coordinates have no common divisor greater than 1, meaning gcd(∣m1∣,…,∣md∣)=1. Let Pd(nd) be the primitive vectors in Hd(nd)∖{0}. Every forbidden hyperplane is represented by a vector in Pd(nd), so we may define, for every integer k≥1,
Bk,m:={v∈[−k,k]d∩Zd:⟨v,m⟩=0},m∈Pd(nd).
The complete forbidden set is Bk:=⋃m∈Pd(nd)Bk,m.
The hyperplane-counting bound [6 Equation (14)] is
Thus, there is a constant Ad>0 such that this proportion is smaller than one for k=⌈Adnd−1⌉. Hence, there is a vector w∈[−k,k]d∩Zd with w∈/Bk. This implies that ⟨w,m⟩=0 for all m∈Pd(nd) and therefore also for all m∈Hd(nd)∖{0}. Its norm satisfies
∥w∥2≤d∥w∥∞≤dk≤d(Ad+1)nd−1.
We may put Cd=d(Ad+1). To obtain a simple curve, we use
v:=w/gcd(∣w1∣,…,∣wd∣).
The length bound L:=∥v∥2≤Cdnd−1 still holds and so do the nonorthogonality conditions. Thus, the curve γ:[0,L]→Td, s↦∥v∥2sv is simple and a hyperbolic nd-design curve on Td.
Sparse frequency sets
For integers d≥2, 1≤r≤d, and t≥1, define the sparse frequency set
Ωd,r(t):={m∈Zd:∥m∥∞≤t,#supp(m)≤r},
where supp(m):={j:mj=0}.
Definition 5.1. For integers d≥2, 1≤r≤d, and t≥1, a rectifiable curve γ:[0,L]→Rd with γ(L)−γ(0)∈Zd, parametrized by arclength, is called an r-sparse t-design curve on Td if
Write w=γ(L)−γ(0)∈Zd. All the functions fa, a∈AI, satisfy the same boundary condition,
fa(L)=(−1)t∑j∈Iwjfa(0).
Thus the periodic or antiperiodic Fourier argument in the proof of Proposition 2.4 applies to this orthonormal family. Bessel’s inequality bounds the total squared Fourier coefficient at each frequency by one, Parseval’s identity gives total mass N, and the sum of the N smallest squared frequencies is at least N(N2−1)/12, so that we obtain
N1a∈AI∑L1∫0L∣fa′(s)∣2ds≥(L2π)212N2−1.
This implies
j∈I∑Ej≥t(t+2)(t+1)2r−1.
Summing over all (rd) choices of I, and observing that each coordinate belongs to (r−1d−1) of them, we obtain
(r−1d−1)L2≥(rd)t(t+2)(t+1)2r−1.
The observation (rd)/(r−1d−1)=d/r yields the first bound in Part (a). The second follows from
t(t+2)(t+1)2r−1=ℓ=0∑r−1(t+1)2ℓ≥t2r−2
and d/r≥1.
(b) For r=1, the primitive vector v=(1,…,1)T gives a simple 1-sparse t-design geodesic of length d.
Suppose r≥2. We use the same counting argument as in the proof of Part (b) in Theorem 4.3. For every integer 1≤s≤t, counting frequencies by their support gives
Let P be the primitive vectors in Ωd,r(t)∖{0}, and define
Bk:=m∈P⋃{w∈[−k,k]d∩Zd:⟨w,m⟩=0}.
Dividing a frequency by the greatest common divisor of its coordinates preserves membership in Ωd,r(t). Thus every forbidden hyperplane is represented by an element of P.
By the hyperplane-counting bound (19) and the union bound,
For sufficiently large cd,r, the forbidden proportion is therefore less than one. Hence there exists w∈[−k,k]d∩Zd such that
⟨w,m⟩=0,∀m∈Ωd,r(t)∖{0}.
The primitive vector v:=w/gcd(∣w1∣,…,∣wd∣) satisfies the same nonorthogonality conditions and leads to a simple curve of length
L:=∥v∥2≤dk≤d(cd,r+1)tr−1.
Thus, Cd,r=d(cd,r+1) is the required constant. □
For r=d, the frequency set Ωd,r(t) is the full tensor-product box, and the lower bound in Theorem 5.2 reduces to Theorem 2.1. For r=1, the diagonal geodesic has minimum length d, independently of t. For intermediate values of r, Theorem 5.2 shows that the optimal order of length is tr−1. In particular, the power of t is determined by the sparsity parameter r, rather than by the ambient dimension d.
Acknowledgement of AI assistance
ChatGPT (OpenAI; model: GPT-6 Astra) was used for discussion of selected proof steps and language editing. The author takes full responsibility for the content of the paper.
Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz 1, A-1090 Vienna, Austria
[1]A. Bondarenko, D. Radchenko, M. Viazovska. Optimal asymptotic bounds for spherical designs. Ann. of Math., 178(2):443–452, 2013.arxiv.org/abs/1009.4407
[2]P. Delsarte, J. M. Goethals, J. J. Seidel. Spherical codes and designs. Geom. Dedicata, 6(3):363–388, 1977.
[3]D. Dung, V. Temlyakov, T. Ullrich. Hyperbolic Cross Approximation. Advanced Courses in Mathematics – CRM Barcelona, Birkhäuser, 2018.
[4]M. Ehler, M. Gräf, S. Neumayer, G. Steidl. Curve based approximation of measures on manifolds by discrepancy minimization. Found. Comput. Math., 21:1595–1642, 2021.
[5]M. Ehler, K. Gröchenig. t-design curves and mobile sampling on the sphere. Forum Math. Sigma, 11:e105, 2023.arxiv.org/abs/2306.13152
[6]M. Forst, L. Fukhansky. Counting basis extensions in a lattice. Proc. Amer. Math. Soc., 150(8):3199–3213, 2022.arxiv.org/abs/2011.05307
[7]R. J. Guenther, W. J. Wilson, D. L. Mohr. Statistical Methods. Academic Press, 3rd ed., 2010.
[8]L. Kämmerer, S. Kunis, D. Potts. Interpolation lattices for hyperbolic cross trigonometric polynomials. J. Complexity, 28(1):76–92, 2012.DOI
[9]E. J. King, D. G. Mixon. Short spherical t-design curves. arXiv:2607.15386, 2026.arxiv.org/abs/2607.15386
[10]S. Kunis. Positive quadrature and mobile sampling of multivariate trigonometric polynomials. arXiv:2608.11915, 2026.arxiv.org/abs/2608.11915
[11]A. Lindblad. Asymptotically optimal t-design curves on S³. arXiv:2408.04044, 2025.arxiv.org/abs/2408.04044
[12]OEIS Foundation Inc. A008288. The On-Line Encyclopedia of Integer Sequences.