An official website of the United States government
Abstract Let f : ℙ 1 → ℙ 1 {f:\mathbb{P}^{1}\to\mathbb{P}^{1}} be a map of degree > 1 {>1} defined over a function field k = K ( X ) {k=K(X)} , where K is a number field and X is a projective curve over K . For each point a ∈ ℙ 1 ( k ) {a\in\mathbb{P}^{1}(k)} satisfying a dynamical stability condition, we prove that the Call–Silverman canonical height for specialization f t {f_{t}} at point a t {a_{t}} , for t ∈ X ( ℚ ¯ ) {t\in X(\overline{\mathbb{Q}})} outside a finite set, induces a Weil height on the curve X ; i.e., we prove the existence of a ℚ {\mathbb{Q}} -divisor D = D f , a {D=D_{f,a}} on X so that the function t ↦ h ^ f t ( a t ) - h D ( t ) {t\mapsto\hat{h}_{f_{t}}(a_{t})-h_{D}(t)} is bounded on X ( ℚ ¯ ) {X(\overline{\mathbb{Q}})} for any choice of Weil height associated to D . We also prove a local version, that the local canonical heights t ↦ λ ^ f t , v ( a t ) {t\mapsto\hat{\lambda}_{f_{t},v}(a_{t})} differ from a Weil function for D by a continuous function on X ( ℂ v ) {X(\mathbb{C}_{v})} , at each place v of the number field K . These results were known for polynomial maps f and all points a ∈ ℙ 1 ( k ) {a\in\mathbb{P}^{1}(k)} without the stability hypothesis,[21, 14],and for maps f that are quotients of endomorphisms of elliptic curves E over k and all points a ∈ ℙ 1 ( k ) {a\in\mathbb{P}^{1}(k)} . [32, 29].Finally, we characterize our stability condition in terms of the geometry of the induced map f ~ : X × ℙ 1 ⇢ X × ℙ 1 {\tilde{f}:X\times\mathbb{P}^{1}\dashrightarrow X\times\mathbb{P}^{1}} over K ; and we prove the existence of relative Néron models for the pair ( f , a ) {(f,a)} , when a is a Fatou point at a place γ of k , where the local canonical height λ ^ f , γ ( a ) {\hat{\lambda}_{f,\gamma}(a)} can be computed as an intersection number.
more »
« less
If You Must Choose Among Your Children, Pick the Right One
Given a simplicial complex K and an injective function f from the vertices of K to R, we consider algorithms that extend f to a discrete Morse function on K. We show that an algorithm of King, Knudson and Mramor can be described on the directed Hasse diagram of K. Our description has a faster runtime for high dimensional data with no increase in space.
more »
« less
- PAR ID:
- 10309897
- Date Published:
- Journal Name:
- Proceedings of the 32nd Canadian Conference on Computational Geometry (CCCG 2020)
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The epsilon-approximate degree, deg_epsilon(f), of a Boolean function f is the least degree of a real-valued polynomial that approximates f pointwise to within epsilon. A sound and complete certificate for approximate degree being at least k is a pair of probability distributions, also known as a dual polynomial, that are perfectly k-wise indistinguishable, but are distinguishable by f with advantage 1 - epsilon. Our contributions are: - We give a simple, explicit new construction of a dual polynomial for the AND function on n bits, certifying that its epsilon-approximate degree is Omega (sqrt{n log 1/epsilon}). This construction is the first to extend to the notion of weighted degree, and yields the first explicit certificate that the 1/3-approximate degree of any (possibly unbalanced) read-once DNF is Omega(sqrt{n}). It draws a novel connection between the approximate degree of AND and anti-concentration of the Binomial distribution. - We show that any pair of symmetric distributions on n-bit strings that are perfectly k-wise indistinguishable are also statistically K-wise indistinguishable with at most K^{3/2} * exp (-Omega (k^2/K)) error for all k < K <= n/64. This bound is essentially tight, and implies that any symmetric function f is a reconstruction function with constant advantage for a ramp secret sharing scheme that is secure against size-K coalitions with statistical error K^{3/2} * exp (-Omega (deg_{1/3}(f)^2/K)) for all values of K up to n/64 simultaneously. Previous secret sharing schemes required that K be determined in advance, and only worked for f=AND. Our analysis draws another new connection between approximate degree and concentration phenomena. As a corollary of this result, we show that for any d <= n/64, any degree d polynomial approximating a symmetric function f to error 1/3 must have coefficients of l_1-norm at least K^{-3/2} * exp ({Omega (deg_{1/3}(f)^2/d)}). We also show this bound is essentially tight for any d > deg_{1/3}(f). These upper and lower bounds were also previously only known in the case f=AND.more » « less
-
We generalize Hermite interpolation with error correction, which is the methodology for multiplicity algebraic error correction codes, to Hermite interpolation of a rational function over a field K from function and function derivative values. We present an interpolation algorithm that can locate and correct <= E errors at distinct arguments y in K where at least one of the values or values of a derivative is incorrect. The upper bound E for the number of such y is input. Our algorithm sufficiently oversamples the rational function to guarantee a unique interpolant. We sample (f/g)^(j)(y[i]) for 0 <= j <= L[i], 1 <= i <= n, y[i] distinct, where (f/g)^(j) is the j-th derivative of the rational function f/g, f, g in K[x], GCD(f,g)=1, g <= 0, and where N = (L[1]+1)+...+(L[n]+1) >= C + D + 1 + 2(L[1]+1) + ... + 2(L[E]+1) where C is an upper bound for deg(f) and D an upper bound for deg(g), which are input to our algorithm. The arguments y[i] can be poles, which is truly or falsely indicated by a function value infinity with the corresponding L[i]=0. Our results remain valid for fields K of characteristic >= 1 + max L[i]. Our algorithm has the same asymptotic arithmetic complexity as that for classical Hermite interpolation, namely soft-O(N). For polynomials, that is, g=1, and a uniform derivative profile L[1] = ... = L[n], our algorithm specializes to the univariate multiplicity code decoder that is based on the 1986 Welch-Berlekamp algorithm.more » « less
-
We study the problem of certification: given queries to a function f : {0,1}n → {0,1} with certificate complexity ≤ k and an input x⋆, output a size-k certificate for f’s value on x⋆. For monotone functions, a classic local search algorithm of Angluin accomplishes this task with n queries, which we show is optimal for local search algorithms. Our main result is a new algorithm for certifying monotone functions with O(k8 logn) queries, which comes close to matching the information-theoretic lower bound of Ω(k logn). The design and analysis of our algorithm are based on a new connection to threshold phenomena in monotone functions. We further prove exponential-in-k lower bounds when f is non-monotone, and when f is monotone but the algorithm is only given random examples of f. These lower bounds show that assumptions on the structure of f and query access to it are both necessary for the polynomial dependence on k that we achieve.more » « less
-
Buchin, Kevin and (Ed.)Given a family F of k-element sets, S₁,…,S_r ∈ F form an r-sunflower if S_i ∩ S_j = S_{i'} ∩ S_{j'} for all i ≠ j and i' ≠ j'. According to a famous conjecture of Erdős and Rado (1960), there is a constant c = c(r) such that if |F| ≥ c^k, then F contains an r-sunflower. We come close to proving this conjecture for families of bounded Vapnik-Chervonenkis dimension, VC-dim(F) ≤ d. In this case, we show that r-sunflowers exist under the slightly stronger assumption |F| ≥ 2^{10k(dr)^{2log^{*} k}}. Here, log^* denotes the iterated logarithm function. We also verify the Erdős-Rado conjecture for families F of bounded Littlestone dimension and for some geometrically defined set systems.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
