MathDB

Miscellaneous (problem 1)

Let a1,a2,a3,…a_1, a_2, a_3, \ldots be a sequence of real numbers (a signal) transmitted in the presence of additive noise such that a1+ϵ1,a2+ϵ2,a3+ϵ3,…a_1 + \epsilon_1, a_2 + \epsilon_2, a_3 + \epsilon_3, \ldots is received (both are infinite sequences). We observe X1,X2,X3,…X_1, X_2, X_3, \ldots which is \emph{either} pure noise ϵ1,ϵ2,ϵ3,…\epsilon_1, \epsilon_2, \epsilon_3, \ldots or the transmitted signal a1+ϵ1,a2+ϵ2,a3+ϵ3,…a_1 + \epsilon_1, a_2 + \epsilon_2, a_3 + \epsilon_3, \ldots. To decide which of the following is received:

(ϵ1,ϵ2,ϵ3,…)∼p(R∞),(a1+ϵ1,a2+ϵ2,a3+ϵ3,…)∼p(R∞),\begin{split} (\epsilon_1, \epsilon_2, \epsilon_3, \ldots) &\sim p(\mathbb{R}^{\infty}),\\ (a_1 + \epsilon_1, a_2 + \epsilon_2, a_3 + \epsilon_3, \ldots) &\sim p(\mathbb{R}^{\infty}), \end{split}

we would like to know whether the measures generated by the sequences above are mutually singular. It is known that if the signal is “strong enough", meaning

∑i=1∞ai2=∞,\sum_{i=1}^\infty a_i^2 = \infty,

then detection is possible. Larry Shepp also noticed that if ϵi\epsilon_i are i.i.d.\ having a pdf such that I(ϵi)I(\epsilon_i) is finite, then the above “strong enough" property is also necessary.

The question is the following. Suppose the signal is weak, i.e.

∑i=1∞ai2<∞,\sum_{i=1}^\infty a_i^2 < \infty,

but

∑i=1∞∣ai∣λ=∞,\sum_{i=1}^\infty |a_i|^{\lambda} = \infty,

for some λ∈(0,2)\lambda \in (0,2). If ϵi∼F\epsilon_i \sim F, what is the infimum of such λ\lambda for which every signal with ∑i=1∞∣ai∣λ=∞\sum_{i=1}^\infty |a_i|^{\lambda} = \infty is detectable.

In the case [−1,+1][-1, +1], the problem has been studied and it is known that the smallest λ\lambda such that detection is possible is λ=1\lambda = 1.

If ϵi∼U(−a,+a)\epsilon_i \sim U(-a, +a), it seems that if P(ϵi=±1)=12P(\epsilon_i = \pm 1) = \frac{1}{2}, a signal with ∑i=1∞∣ai∣λ=∞\sum_{i=1}^\infty |a_i|^{\lambda} = \infty for some λ>0\lambda > 0 is detectable so that in this case the infimum equals 00.

Equivalent formulations 8Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. Miscellaneous (problem 1)

    Parameters: n≥2n \geq 2 and α>0\alpha > 0. Given independent uniformly random x1,x2,⋯∈Sn−1={v∈Rn:∥v∥2=1}x_1, x_2, \dots\in S^{n-1} = \{v \in \mathbb R^n: \|v\|_2 = 1\}, how quickly can we find a subsequence that covers Sn−1S^{n-1}? (Here, “covers" means that every point of Sn−1S^{n-1} is within angle α\alpha of a point in the subsequence.) For example, consider the case when n=1000n = 1000 and α=75∘\alpha = 75^\circ.

    source: AimPL: Quantum algorithms for analysis of public-key crypto (posed by John Schanck)

  2. Miscellaneous (problem 1)

    Let GG hyperbolic, acting geometrically on X0,X1X_0,X_1. Is there a quasi-isometry X0→X1X_0\rightarrow X_1 with smallest multiplicative constant?

    source: AimPL: Boundaries of groups (posed by Lafont)

  3. Miscellaneous (problem 1)

    If GG is a free-by-cyclic group then Out(G)\mathrm{Out}(G) is of type VFVF.

    source: AimPL: Rigidity properties of free-by-cyclic groups (posed by Naomi Andrew)

  4. Miscellaneous (problem 1)

    \begin{enumerate}[a.] \item Is every FF Borel Ramsey? We are especially interested in not spherical FF. \item If FF is Borel Ramsey, is it Ramsey? \end{enumerate}

    source: AimPL: Descriptive graph theory

  5. Miscellaneous (problem 1)

    Can one calculate moments of zeta closer to the σ=1\sigma=1 line instead of on the σ=12\sigma=\frac{1}{2} line? Can one also identify the lower order terms in the σ=1\sigma=1 case?

    source: AimPL: Moments of zeta and correlations of divisor sums (posed by T. Wooley)

  6. Miscellaneous (problem 1)

    Prove or disprove the following conjecture.

    Let KK be a global field, let vv be a place of KK, and let XX and YY be projective varieties which are not singletons. Suppose that X(K)X(K) is Zariski dense in XX. Given a dominant rational map f:X⇢Yf: X \dashrightarrow Y and a nonempty Zariski open set U⊂XU\subset X, there is a Cartier divisor D>0D > 0 on YY, defined over KK, such that some sequence of points in (U∖f∗D)(K)(U \setminus f^*D)(K) approaches f∗Df^*D vv-adically.

    source: AimPL: Definability and decidability problems in number theory (posed by Hector Pasten)

  7. Miscellaneous (problem 1)

    Is a random walk on Ball(t){\rm Ball}(t) recurrent? What if the jump rate of the walker is allowed to depend on tt?

    source: AimPL: First passage percolation (posed by Amir Dembo)

  8. Miscellaneous (problem 1)

    If two smooth manifolds M1M_1 and M2M_2 are homeomorphic, could their spaces of Engel structures be used to distinguish them smoothly?

    source: AimPL: Engel structures

References

Primary source

AimPL: Entropy power inequalities (posed by Abram Kagan)

cryptographylogicnumber-theoryprobabilitytopology
InAIM Problem Lists
Posted

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.