# Questions tagged [discrepancy-theory]

The tag has no usage guidance.

38 questions
Filter by
Sorted by
Tagged with
39 views

41 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 ...
48 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$ ...
72 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}$ ...
125 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 ...
428 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  ...
51 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 ...
277 views

44 views

185 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))}.$$ ...
199 views

303 views

225 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 ...
374 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$ ...
126 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{...
243 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 ...
58 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 ...
102 views

### Beck-Fiala for other discrepancies

Is there an analogue of the Beck-Fiala theorem for linear or hereditary discrepancies of hypergraphs?
324 views

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 ...
146 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? ...
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\}$ ...