Questions tagged [discrepancy-theory]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
11 votes
2 answers
617 views

Can we balance $2$-powers?

If a sequence of reals $-1<x_1,\dots,x_k<1$ satisfies \begin{equation*} x_{i+1}= \begin{cases} 2x_i, & \text{if } 2|x_i|<1 \\ 2x_i-2, & \text{...
domotorp's user avatar
  • 18.3k
1 vote
0 answers
70 views

Some question on Lovett-Meka Discrepancy Minimisation Algorithm

I am reading the paper Constructive Discrepancy Minimization by Walking on The Edges which finds the discrepancy of a set system matching Spencer's bound, in randomised polynomial time. In short, ...
Sudipta Roy's user avatar
7 votes
0 answers
156 views

Partly online discrepancy for intervals

Assume that the numbers $\{1,\dots,n\}$ arrive in some unknown order. Each number needs to be colored red or blue upon arrival. What is the best discrepancy we can maintain for the intervals? I know ...
domotorp's user avatar
  • 18.3k
4 votes
0 answers
97 views

L_infinity norm of signed sums of Fourier characters and discrepancy of Fourier matrices

Consider signed sums $\displaystyle A_f(x) =\sum_{\chi} (-1)^{f(\chi)} \chi(x)$ for some set $S$ of characters of an abelian group $G$, and signing $f$ of the characters. For a fixed set $S$ what is ...
fourier_discrepancy's user avatar
3 votes
1 answer
158 views

Minimize total area bounded by $N$ lines in general position

Suppose we have $N$ lines in general position (any two lines, but no three lines, meet at a point) ($N\geq 3$). Let the smallest bounded region have area $1$. Determine the minimum (or possibly ...
Lieutenant Zipp's user avatar
2 votes
0 answers
308 views

Distribution of $\frac{(\sin(n))^2}{2^n}$ in dyadic intervals?

Good morning all, I was wondering what kind of methods could help in order to tackle the following problem : Define the set $A = \left\{ \frac{(\sin(n))^2}{2^n}\right\}$ for $n$ integer. So A is a ...
Anthony's user avatar
  • 21
4 votes
0 answers
157 views

Can resolution of the Kadison-Singer Problem provide progress on the Komlos Conjecture?

This is not a concrete question, just some thoughts. The Komlos Conjecture is as follows- There exists an absolute constant $C>0$, such that the following holds: For all $d$ and any set of vectors ...
Sudipta Roy's user avatar
1 vote
2 answers
163 views

Estimates on the discrepancy of random sequences

The discrepancy of a $[0,1]$-valued sequence $n \mapsto \alpha_n$ is the quantity $$D(N; \alpha) \stackrel{\text{def}}{=} \sup_{(a,b) \subset [0,1]} \left|\frac{\#\{1 \leq n \leq N : \alpha_n \in (a,b)...
Arsh Jhaj's user avatar
  • 123
1 vote
0 answers
88 views

Partial crepant resolution in codimension 2

Let $\xi_5$ be a 5-root of the unity. We consider $\mathbb{C}^4/G$, where $G=\left\langle \sigma,\tau\right\rangle$, with $\sigma$ and $\tau$ the automorphisms given, respectively, by the following ...
Kovalevskaia's user avatar
2 votes
0 answers
45 views

Source request: Optimal bounds on signings of points from a convex body

I recently came across an old survey of problems in discrete geometry: https://pdfs.semanticscholar.org/c350/f4d4a9466fa6708d99ec1187c63d89bed20f.pdf Problem 2.1 from the list caught my eye. It states ...
Arun Jambulapati's user avatar
1 vote
1 answer
177 views

Is the bound of Spencer on discrepancy tight?

Suppose $\mathcal{S} = \{S_1,\ldots,S_m\}$ is a set system in $[n]=\{1,\ldots,n\}$, which means that for each $i$, $S_i\subset [n].$ Define the discrepancy of $\mathcal{S}$ by $$disc(\mathcal{S})=\...
Nate's user avatar
  • 131
1 vote
0 answers
55 views

Diophantine bound for homogeneous system under norm conditions for solutions and system

If $b_{ij}\in[0,2^t-1]\cap\mathbb Z$ holds at every $i\in\{1,\dots,k'\}$ and $j\in\{1,\dots,k\}$ where $1\leq k'\leq k$ holds then there are $x_1,\dots,x_k\in\mathbb Z:\sum_{j=1}^kx_jb_{1i}=0\wedge\...
VS.'s user avatar
  • 1,816
2 votes
1 answer
132 views

Reference request - parallel rectangles discrepancy theory

I've been reading about discrepancy theory and trying to understand some of the open problems in the field. Wikipedia has a list of some of the open problems, but the descriptions are terrible. In ...
DJA's user avatar
  • 425
1 vote
0 answers
51 views

Beck-Fiala Discrepency Type Results for Arbitrary Graph Labelings

Suppose we have a graph $G$ on $n$ vertices $x_1 , \dots, x_n$ attached with weights of values from $1$ to $n$. We will write $\text{weight}(x_i)$ as simply $x_i$ and let $\text{diff}(G) = \min _{(x_i,...
Raj Raina's user avatar
  • 139
2 votes
1 answer
99 views

Discrepancy of the Halton set

I am interested in low discrepancy sets for its applications in Monte Carlo integration - KH inequality tells us that the error will be lesser if the discrepancy of the sample is lesser. Every ...
Divakaran Divakaran's user avatar
4 votes
0 answers
65 views

Lower and upper (combinatorial) discrepancy

(I will state my question in terms of combinatorial discrepancy, but the same could be also asked about measure-theoretic discrepancy as well.) The combinatorial discrepancy of a family $\mathcal F$ ...
domotorp's user avatar
  • 18.3k
1 vote
0 answers
95 views

Smallest integer lattice point by box measure in a polytope?

Given an integer lattice $\mathcal L\subseteq\mathbb Z^n$ represented by basis $\mathcal B$ and an integer linear program $Ax\leq b$ where $x\in\mathbb Z^n$ is unknown with $A\in\mathbb Z^{m\times n}$ ...
Turbo's user avatar
  • 13.6k
1 vote
0 answers
132 views

Probability of small solutions to an uniform random linear diophantine equation?

Take the set $$T(c_1,\dots,c_t)=\{(x_1,\dots,x_t)\in\mathbb Z^t\backslash\{(0,\dots,0)\}:\sum_{i=1}^tc_ix_i\equiv0\bmod q\}$$ where $c_1,\dots,c_t\in(-q/2,q/2)\cap\mathbb Z$. What is probability ...
Turbo's user avatar
  • 13.6k
3 votes
1 answer
552 views

Typo in Soundararajan's *Bulletin of the AMS* article on Tao's resolution of The Erdos Discrepancy Problem?

I think that there is a typo in the paper referred to in the title of the question, available here. While discussing Roth's proof of AP discrepancy, on page 2, the author states that Roth [20] ...
kodlu's user avatar
  • 10k
1 vote
0 answers
64 views

Spherical code for interesection of $k$-sparse vectors and unit sphere

Let us assume $X\in\mathbb{R}^{n\times d}, rank(X)=d$, integer $k\in\mathbb{N},k\ll d$, positive constant $0<\epsilon<1$, and $\mathcal{S}\subset \mathbb{R}^d$ denotes the unit sphere. We also ...
kvphxga's user avatar
  • 175
7 votes
0 answers
293 views

4-tuples with close sums

Some $4$-tuples of positive real numbers $(a_1,b_1,c_1,d_1),\dots,(a_n,b_n,c_n,d_n)$ are given, with all $a_i,b_i,c_i,d_i\leq 1$. Is it always possible to partition $\{1,2,\dots,n\}$ into two subsets $...
pi66's user avatar
  • 1,199
2 votes
0 answers
67 views

Discrepancy related independent vector from tensor product?

Here discrepancy is from $(2.4)$ in https://www.ricam.oeaw.ac.at/files/people/siambook_nied.pdf given by 'The discrepancy $D_N(P) = D_N(x_l,\dots,X_N)$ of the point set $P$ of $N$ points in $\mathbb Z^...
Turbo's user avatar
  • 13.6k
1 vote
0 answers
53 views

Discrepancy bound of integer tensor product sequence?

Here discrepancy is from $(2.4)$ in https://www.ricam.oeaw.ac.at/files/people/siambook_nied.pdf given by 'The (extreme) discrepancy $D_N(P) = D_N(x_l,\dots,X_N)$ of the point set $P$ of $N$ points in $...
Turbo's user avatar
  • 13.6k
1 vote
0 answers
47 views

Does a weighted sequence derived from a sequence matching the Siegel lemma BV bound behave as an uniformly random sequence?

Pick integers $r_1',\dots,r_t'$ that achieve the Bombieri Vaaler bound for the Siegel lemma and find an $m$ (it exists by Dirichlet Pigeonhole) such that given prime $T$ gets $m(r_1',\dots,r_t')\equiv(...
Turbo's user avatar
  • 13.6k
1 vote
0 answers
191 views

On discrepancy properties of $\{0,\pm1\}$ sequences arising from cyclotomic polynomials

Given $n=2^k p^r q^m$ take a $d\in\Bbb Z$ with $d\mid n$ such that each $a_i$ is in $\{0,\pm1\}$ in $$f_{d,n}(x)=\frac{x^n-1}{\Phi_d(x)}=a_0+a_1x+\cdots+a_{\deg(f_{d,n}(x))}x^{\deg(f_{d,n}(x))}.$$ ...
Turbo's user avatar
  • 13.6k
5 votes
2 answers
228 views

Bounded version of linear and quadratic Hasse--Minkowski theorem

The Hasse-Minkowski theorem states that if $$Q(x_1,\ldots,x_n) = \sum_{i,j=1}^n a_{ij} x_ix_j$$ is a quadratic form with $a_{ij} \in \mathbb Z$ and $\det (a_{ij}) \neq 0$, then the equation $$Q(x_1,\...
Turbo's user avatar
  • 13.6k
2 votes
2 answers
85 views

Discrepancy bounds for moderate points counts in dimensions from d=2 to 32?

In one dimension d=1 an equally-spaced set of N points in [0,1) has the lowest possible (star) discrepancy D=0.5/N. Unfortunately, I found only asymptotic bounds for other dimensions (e.g. acc. to ...
user32038's user avatar
  • 121
18 votes
3 answers
2k views

Current state of the Komlos conjecture on vector balancing

Komlos Conjecture: the exists an absolute constant $K>0$ such that for all $d$ and any collection of vectors $v_1,\ldots, v_n\in \mathbb{R}^d$ with $\left\lVert v_i\right\rVert _2=1$ we can find ...
TOM's user avatar
  • 2,218
1 vote
1 answer
115 views

Quantified imbalance in signed graphs

Let $G=(V,E)$ be an $n$-vertex simple undirected graph. A signing of the graph is a function $s:E \to \{1,-1\}$, and $(G,s)$ is a signed graph. That is, we label each edge of the graph with $1$ or $-1$...
BharatRam's user avatar
  • 939
2 votes
1 answer
246 views

Distribution-free statistics on compact Lie groups

(Cross-listed from the math stackexchange) Let $(X_i)_{i=1}^n$ be iid random variables with joint cdf $F$. Recall that the empirical distribution function is: $$ F_n(x) = \frac{1}{n} \sum_{i=1}^n \...
Daniel Miller's user avatar
3 votes
0 answers
332 views

On discrepancy of integer sequences related to Erdos-Turan-Koksma

Assume we have a sequence $a_1,\dots,a_k\in\Bbb N$ with each $a_i\approx n$ where $n$ is some integer. Suppose there exists an $\eta\in(0,1)$ such that for every $d_1,\dots,d_k\in\Bbb Z$ with $$...
user avatar
2 votes
2 answers
724 views

Occurrence of simultaneous small remainders?

Fix $(a,b)=1$, $a<b<2a$ and $a,b>n^{1/(2t)}$ and fix a prime $T\approx n^{\tau+\frac1k}$ where $\tau\geq1$ and $k=2(t-1)$. We can show using exponential sums there is an $m_{_T}$ such that $T/...
user avatar
2 votes
1 answer
299 views

the sum of fractional parts times the ordinary powers

Is there any way to compute/express $\sum\limits^m_{i=0}\{\frac{q*i}{m}\}(\frac{i}{m})^n$ ? Here $q,m,n$ are natural numbers, one can assume $gcd(q,m)=1$. Furthermore, $n$ can be treated as a ...
Dmitry Kerner's user avatar
0 votes
0 answers
95 views

Criterion for irrational numbers of constant type 2

From Kuiper's and Niederreiter's book Uniform distribution of sequences, Ch.2, § 3, I learn that an irrational number $\alpha\in \mathbf{R}\smallsetminus \mathbf{Q}$ is of constant type $\eta$ if ...
Daniel Miller's user avatar
2 votes
0 answers
76 views

What do you call the collection of all sets shattered by $F$?

The proof of Pajor's lemma uses the collection of all sets $S\subseteq X$ shattered by some $F\subseteq 2^X$. Is there a standard term for the former object? I've been privately referring to it as the ...
Aryeh Kontorovich's user avatar
4 votes
0 answers
142 views

Balanced partitions of vector sets

We are interested in the following Lemma. Let $V\subset [0,1]^n\subset\mathbb R^n$ be a set of $n$-dimensional vectors. Then for each $r\le |V|$ there exists a partition $$V=V_1\cup V_2\cup\dots \cup ...
Alex Ravsky's user avatar
  • 4,092
3 votes
1 answer
237 views

An extremal combinatorics problem involving column summation

Given $n\in\Bbb N$, $\alpha>0$, $\beta\in\big[\frac12,1\big]$ denote $\mathcal R_{n,\alpha,\beta}$ as collection of all $2^n\times 2^{n^\alpha}$ $0/1$ matrices with every row summing to strictly ...
user avatar
5 votes
1 answer
601 views

How are the infinity norm of Fourier transforms of sign vectors distributed?

This is a follow up to an earlier resolved question. Define the $n$-dimensional discrete Fourier transform via the matrix $$ D_{s,t} := \omega^{st}, $$ where $\omega=\exp(-2\pi i/n)$. Notice that $D$ ...
MERTON's user avatar
  • 505
2 votes
0 answers
140 views

error estimate of linear interpolation in high dimension

Consider convex functions $f,g$ on $[0,1]^d$. Let $x_1,\cdots,x_n$ be $n\geq d+1$ fixed point in $[0,1]^d$ that is equally 'distributed' in the sense that $$c_1\leq \frac{n\mathrm{vol}(K)}{\mathrm{...
Roy Han's user avatar
  • 589
5 votes
1 answer
265 views

$L^2$ discrepancy bound for sequences in $[0,1)$

Given a sequence $x_1,x_2,\dots$, let $D_n$ be the $L^2$-norm of the function $f_n$ whose value at $t \in [0,1)$ is $nt$ minus the number of $1 \leq i \leq n$ with $x_i \leq t$. What can be said ...
James Propp's user avatar
  • 19.4k
1 vote
1 answer
70 views

How to compute hereditary discrepancy

I want to compute exactly the hereditary discrepancy of a small (on up to 20 points) set system - is there an efficient way to do it? Brute force search over the discrepancies of all subsystems seems ...
Felix Goldberg's user avatar
1 vote
1 answer
139 views

Beck-Fiala for other discrepancies

Is there an analogue of the Beck-Fiala theorem for linear or hereditary discrepancies of hypergraphs?
Felix Goldberg's user avatar
7 votes
1 answer
336 views

Maximal disarrangement of $n \times n$ numbers

This question is inspired by Martin Erickson's question, "Labeling a Square Array." I'll start by quoting Martin: the $n^2$ cells of an $n \times n$ array are labeled with the integers $1, \dots, ...
Joseph O'Rourke's user avatar
10 votes
1 answer
595 views

Are shift-chains two-colorable?

For $A\subset [n]$ denote by $a_i$ the $i^{th}$ smallest element of $A$. For two $k$-element sets, $A,B\subset [n]$, we say that $A\le B$ if $a_i\le b_i$ for every $i$. A $k$-uniform hypergraph ${\...
domotorp's user avatar
  • 18.3k
12 votes
3 answers
1k views

Distribution of fractional parts of n^{3/2}

What can be said about the limiting distribution of the sequence of fractional parts of $\{n^{a},n>0\}$ for $a\in(1,2)$. I ran a computer experiment for $n\sqrt{n}$ and it looks like uniformly ...
Zarathustra's user avatar
  • 1,404
7 votes
1 answer
156 views

If every point is contained in at most 3 sets and all sets are big, then is the discrepancy zero?

Suppose we have a finite, 100-uniform system of sets such that any point is contained in at most 3 sets. Is it true that we can color the points such that every set contains 50 red and 50 blue points? ...
domotorp's user avatar
  • 18.3k
42 votes
8 answers
4k views

1 rectangle <= 4 squares

Almost 25 years ago a professor at Indiana U showed me the following problem: given a map $\mathbb{Z}^2\rightarrow\mathbb{R}$ such that the sum inside every square (parallel to the axes) is $\leq1$ ...
5 votes
2 answers
924 views

Helm's improvement to Beck-Fiala theorem

Beck-Fiala theorem states that if $X$ is a finite set and $H$ is any family of subsets of $X$, in which every vertex occurs in at most $d$ sets of $H$, then there is a function $f\colon X\to\{1,-1\}$ ...
Boris Bukh's user avatar
  • 7,746