An official website of the United States government
Let $$\omega(n)$$ denote the number of distinct prime factors of $$n$$. Assuming a suitably uniform version of the prime $$k$$-tuples conjecture, we show that the number \begin{align*} \sum_{n=1}^\infty \frac{\omega(n)}{2^n} \end{align*} is irrational. This settles (conditionally) a question of Erd\H{o}s.
more »
« less
Distinct Angles and Angle Chains in Three Dimensions
In 1946, Erd\H{o}s posed the distinct distance problem, which seeks to findthe minimum number of distinct distances between pairs of points selected fromany configuration of $$n$$ points in the plane. The problem has since beenexplored along with many variants, including ones that extend it into higherdimensions. Less studied but no less intriguing is Erd\H{o}s' distinct angleproblem, which seeks to find point configurations in the plane that minimizethe number of distinct angles. In their recent paper "Distinct Angles inGeneral Position," Fleischmann, Konyagin, Miller, Palsson, Pesikoff, and Wolfuse a logarithmic spiral to establish an upper bound of $$O(n^2)$ on the minimumnumber of distinct angles in the plane in general position, which prohibitsthree points on any line or four on any circle. We consider the question of distinct angles in three dimensions and providebounds on the minimum number of distinct angles in general position in thissetting. We focus on pinned variants of the question, and we examine explicitconstructions of point configurations in $$\mathbb{R}^3$$ which useself-similarity to minimize the number of distinct angles. Furthermore, westudy a variant of the distinct angles question regarding distinct angle chainsand provide bounds on the minimum number of distinct chains in $$\mathbb{R}^2$$and $$\mathbb{R}^3$$.
more »
« less
- Award ID(s):
- 1947438
- PAR ID:
- 10401049
- Date Published:
- Journal Name:
- Discrete Mathematics & Theoretical Computer Science
- Volume:
- vol. 25:1
- Issue:
- Combinatorics
- ISSN:
- 1365-8050
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract A bipartite graph $$H = \left (V_1, V_2; E \right )$$ with $$\lvert V_1\rvert + \lvert V_2\rvert = n$$ is semilinear if $$V_i \subseteq \mathbb {R}^{d_i}$$ for some $$d_i$$ and the edge relation E consists of the pairs of points $$(x_1, x_2) \in V_1 \times V_2$$ satisfying a fixed Boolean combination of s linear equalities and inequalities in $$d_1 + d_2$$ variables for some s . We show that for a fixed k , the number of edges in a $$K_{k,k}$$ -free semilinear H is almost linear in n , namely $$\lvert E\rvert = O_{s,k,\varepsilon }\left (n^{1+\varepsilon }\right )$$ for any $$\varepsilon> 0$$ ; and more generally, $$\lvert E\rvert = O_{s,k,r,\varepsilon }\left (n^{r-1 + \varepsilon }\right )$$ for a $$K_{k, \dotsc ,k}$$ -free semilinear r -partite r -uniform hypergraph. As an application, we obtain the following incidence bound: given $$n_1$$ points and $$n_2$$ open boxes with axis-parallel sides in $$\mathbb {R}^d$$ such that their incidence graph is $$K_{k,k}$$ -free, there can be at most $$O_{k,\varepsilon }\left (n^{1+\varepsilon }\right )$$ incidences. The same bound holds if instead of boxes, one takes polytopes cut out by the translates of an arbitrary fixed finite set of half-spaces. We also obtain matching upper and (superlinear) lower bounds in the case of dyadic boxes on the plane, and point out some connections to the model-theoretic trichotomy in o -minimal structures (showing that the failure of an almost-linear bound for some definable graph allows one to recover the field operations from that graph in a definable manner).more » « less
-
Mestre, Julián; Wirth, Anthony (Ed.)For a set of red and blue points in the plane, a minimum bichromatic spanning tree (MinBST) is a shortest spanning tree of the points such that every edge has a red and a blue endpoint. A MinBST can be computed in O(n log n) time where n is the number of points. In contrast to the standard Euclidean MST, which is always plane (noncrossing), a MinBST may have edges that cross each other. However, we prove that a MinBST is quasi-plane, that is, it does not contain three pairwise crossing edges, and we determine the maximum number of crossings. Moreover, we study the problem of finding a minimum plane bichromatic spanning tree (MinPBST) which is a shortest bichromatic spanning tree with pairwise noncrossing edges. This problem is known to be NP-hard. The previous best approximation algorithm, due to Borgelt et al. (2009), has a ratio of O(√n). It is also known that the optimum solution can be computed in polynomial time in some special cases, for instance, when the points are in convex position, collinear, semi-collinear, or when one color class has constant size. We present an O(log n)-factor approximation algorithm for the general case.more » « less
-
Algorithmic Decorrelation and Planted Clique in Dependent Random Graphs: The Case of Extra TrianglesWe aim to understand the extent to which the noise distribution in a planted signal-plus-noise problem impacts its computational complexity. To that end, we consider the planted clique and planted dense subgraph problems, but in a different ambient graph. Instead of Erd\H{o}s-R\'enyi , which has independent edges, we take the ambient graph to be the \emph{random graph with triangles} (RGT) obtained by adding triangles to . We show that the RGT can be efficiently mapped to the corresponding , and moreover, that the planted clique (or dense subgraph) is approximately preserved under this mapping. This constitutes the first average-case reduction transforming dependent noise to independent noise. Together with the easier direction of mapping the ambient graph from Erd\H{o}s-R\'enyi to RGT, our results yield a strong equivalence between models. In order to prove our results, we develop a new general framework for reasoning about the validity of average-case reductions based on \emph{low sensitivity to perturbations}.more » « less
-
Abstract We prove that among all 1-periodic configurations $$\Gamma $$ of points on the real line $$\mathbb{R}$$ the quantities $$\min _{x \in \mathbb{R}} \sum _{\gamma \in \Gamma } e^{- \pi \alpha (x - \gamma )^{2}}$$ and $$\max _{x \in \mathbb{R}} \sum _{\gamma \in \Gamma } e^{- \pi \alpha (x - \gamma )^{2}}$$ are maximized and minimized, respectively, if and only if the points are equispaced and whenever the number of points $$n$$ per period is sufficiently large (depending on $$\alpha $$). This solves the polarization problem for periodic configurations with a Gaussian weight on $$\mathbb{R}$$ for large $$n$$. The first result is shown using Fourier series. The second result follows from the work of Cohn and Kumar on universal optimality and holds for all $$n$$ (independent of $$\alpha $$).more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.46298/dmtcs.10037
