# Questions tagged [discrepancy-theory]

The tag has no usage guidance.

48 questions
Filter by
Sorted by
Tagged with
609 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{...
• 18.2k
1 vote
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, ...
• 148
154 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 ...
• 18.2k
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 ...
154 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 ...
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 ...
• 21
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 ...
• 148
1 vote
161 views

• 131
1 vote
55 views

• 139
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 ...
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$ ...
• 18.2k
1 vote
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}$ ...
• 13.6k
1 vote
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 ...
• 13.6k
549 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] ...
• 10k
1 vote
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 ...
• 175
293 views

• 13.6k
1 vote
53 views

• 13.6k
1 vote
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))}.$$ ...
• 13.6k
228 views

• 5,599
331 views

• 4,027
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 ...
600 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$ ...
• 505
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{...
• 589
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 ...
• 19.3k
1 vote
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 ...
• 6,862
1 vote
138 views

### Beck-Fiala for other discrepancies

Is there an analogue of the Beck-Fiala theorem for linear or hereditary discrepancies of hypergraphs?
• 6,862
336 views

• 18.2k
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 ...
• 1,394
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? ...
• 18.2k
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$ ...
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\}$ ...