An official website of the United States government
Given a function f on (F_2_^n, we study the following problem. What is the largest affine subspace U such that when restricted to U, all the non-trivial Fourier coefficients of f are very small? For the natural class of bounded Fourier degree d functions f : (F_2)^n → [−1, 1], we show that there exists an affine subspace of dimension at least ˜Ω (n^(1/d!) k^(−2)), wherein all of f ’s nontrivial Fourier coefficients become smaller than 2^(−k) . To complement this result, we show the existence of degree d functions with coefficients larger than 2^(−d log n) when restricted to any affine subspace of dimension larger than Ω(dn^(1/(d−1))). In addition, we give explicit examples of functions with analogous but weaker properties. Along the way, we provide multiple characterizations of the Fourier coefficients of functions restricted to subspaces of (F_2)^n that may be useful in other contexts. Finally, we highlight applications and connections of our results to parity kill number and affine dispersers.
more »
« less
This content will become publicly available on December 4, 2025
Constructions of bounded solutions of div u = f in critical spaces
We construct uniformly bounded solutions of the equation div u = f for arbitrary data f in the critical spaces Ld(Ω), where Ω is a domain of Rd. This question was addressed by Bourgain & Brezis, [BB2003], who proved that although the problem has a uniformly bounded solution, it is critical in the sense that there exists no linear solution operator for general Ld-data. We first discuss the validity of this existence result under weaker conditions than f ∈ Ld(Ω), and then focus our work on constructive processes for such uniformly bounded solutions. In the d = 2 case, we present a direct one-step explicit construction, which generalizes for d > 2 to a (d − 1)-step construction based on induction. An explicit construction is proposed for compactly supported data in L2,∞(Ω) in the d = 2 case. We also present constructive approaches based on optimization of a certain loss functional adapted to the problem. This approach provides a two-step construction in the d = 2 case. This optimization is used as the building block of a hierarchical multistep process introduced in [Tad2014] that converges to a solution in more general situations.
more »
« less
- Award ID(s):
- 2134077
- PAR ID:
- 10564825
- Publisher / Repository:
- Springer
- Date Published:
- ISSN:
- 978-3-031-75802-7
- Page Range / eLocation ID:
- 177-200
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Abstract We consider the 𝑑-dimensional Boussinesq system defined on a sufficiently smooth bounded domain and subject to a pair { v , u } \{v,\boldsymbol{u}\} of controls localized on { Γ ~ , ω } \{\widetilde{\Gamma},\omega\} .Here, 𝑣 is a scalar Dirichlet boundary control for the thermal equation, acting on an arbitrarily small connected portion Γ ~ \widetilde{\Gamma} of the boundary Γ = ∂ Ω \Gamma=\partial\Omega .Instead, 𝒖 is a 𝑑-dimensional internal control for the fluid equation acting on an arbitrarily small collar 𝜔 supported by Γ ~ \widetilde{\Gamma} .The initial conditions for both fluid and heat equations are taken of low regularity.We then seek to uniformly stabilize such Boussinesq system in the vicinity of an unstable equilibrium pair, in the critical setting of correspondingly low regularity spaces, by means of an explicitly constructed, finite-dimensional feedback control pair { v , u } \{v,\boldsymbol{u}\} localized on { Γ ~ , ω } \{\widetilde{\Gamma},\omega\} .In addition, they will be minimal in number and of reduced dimension; more precisely, 𝒖 will be of dimension ( d - 1 ) (d-1) , to include necessarily its 𝑑-th component, and 𝑣 will be of dimension 1.The resulting space of well-posedness and stabilization is a suitable, tight Besov space for the fluid velocity component (close to L 3 ( Ω ) \boldsymbol{L}^{3}(\Omega) for d = 3 d=3 ) and a corresponding Besov space for the thermal component, q > d q>d .Unique continuation inverse theorems for suitably over-determined adjoint static problems play a critical role in the constructive solution.Their proof rests on Carleman-type estimates, a topic pioneered by M. V. Klibanov since the early 80s.more » « less
-
LaValle, Steve M.; Lin, Ming; Ojala, Timo; Shell, Dylan; Yu, Jingjin (Ed.)The line coverage problem is the task of servicing a given set of one-dimensional features in an environment. Its applications include the inspection of road networks, power lines, and oil and gas lines. The line coverage problem is a generalization of the standard arc routing problems, and is NP-hard in general. We address the single robot line coverage problem where the service and deadhead costs are distinct and asymmetric. We model the problem as an optimization problem that minimizes the total cost of travel on a given graph. We present approximation algorithms to obtain bounded solutions efficiently, using the minimum cost flow problem. We build the main algorithm in stages by considering three simpler subproblems. The subproblems are based on the structure of the required graph, i.e., the graph induced by the features that require servicing. We fi rst present an optimal algorithm for the case of Eulerian graphs with only required edges. Next we consider general graphs, not necessarily Eulerian, with only required edges and present a 2-approximation algorithm. Finally, we consider the general case with both required and non-required edges. The approximation algorithm is dependent on the Asymmetric Traveling Salesperson Problem (ATSP), and is bounded by alpha(C) + 2, where alpha(C) is the approximation factor of the ATSP algorithm with C connected components. Our upper bound is also an improvement over the existing results for the asymmetric rural postman problem.more » « less
-
Abstract This is a continuation, and conclusion, of our study of bounded solutions u of the semilinear parabolic equation $$u_t=u_{xx}+f(u)$$ u t = u xx + f ( u ) on the real line whose initial data $$u_0=u(\cdot ,0)$$ u 0 = u ( · , 0 ) have finite limits $$\theta ^\pm $$ θ ± as $$x\rightarrow \pm \infty $$ x → ± ∞ . We assume that f is a locally Lipschitz function on $$\mathbb {R}$$ R satisfying minor nondegeneracy conditions. Our goal is to describe the asymptotic behavior of u ( x , t ) as $$t\rightarrow \infty $$ t → ∞ . In the first two parts of this series we mainly considered the cases where either $$\theta ^-\ne \theta ^+$$ θ - ≠ θ + ; or $$\theta ^\pm =\theta _0$$ θ ± = θ 0 and $$f(\theta _0)\ne 0$$ f ( θ 0 ) ≠ 0 ; or else $$\theta ^\pm =\theta _0$$ θ ± = θ 0 , $$f(\theta _0)=0$$ f ( θ 0 ) = 0 , and $$\theta _0$$ θ 0 is a stable equilibrium of the equation $${{\dot{\xi }}}=f(\xi )$$ ξ ˙ = f ( ξ ) . In all these cases we proved that the corresponding solution u is quasiconvergent—if bounded—which is to say that all limit profiles of $$u(\cdot ,t)$$ u ( · , t ) as $$t\rightarrow \infty $$ t → ∞ are steady states. The limit profiles, or accumulation points, are taken in $$L^\infty _{loc}(\mathbb {R})$$ L loc ∞ ( R ) . In the present paper, we take on the case that $$\theta ^\pm =\theta _0$$ θ ± = θ 0 , $$f(\theta _0)=0$$ f ( θ 0 ) = 0 , and $$\theta _0$$ θ 0 is an unstable equilibrium of the equation $${{\dot{\xi }}}=f(\xi )$$ ξ ˙ = f ( ξ ) . Our earlier quasiconvergence theorem in this case involved some restrictive technical conditions on the solution, which we now remove. Our sole condition on $$u(\cdot ,t)$$ u ( · , t ) is that it is nonoscillatory (has only finitely many critical points) at some $$t\ge 0$$ t ≥ 0 . Since it is known that oscillatory bounded solutions are not always quasiconvergent, our result is nearly optimal.more » « less
-
We introduce and study the problem of dueling optimization with a monotone adversary, a generalization of (noiseless) dueling convex optimization. The goal is to design an online algorithm to find a minimizer x* for a function f:X→R, for X \subseteq R^d. In each round, the algorithm submits a pair of guesses x1 and x2, and the adversary responds with any point in the space that is at least as good as both guesses. The cost of each query is the suboptimality of the worst of the two guesses; i.e., max(f(x1) − f(x*),f(x2) − f(x*)). The goal is to minimize the number of iterations required to find an ε-optimal point and to minimize the total cost (regret) of the guesses over many rounds. Our main result is an efficient randomized algorithm for several natural choices of the function f and set X that incurs cost O(d) and iteration complexity O(d log(1/ε)^2). Moreover, our dependence on d is asymptotically optimal, as we show examples in which any randomized algorithm for this problem must incur Ω(d) cost and iteration complexity.more » « less
