# Questions tagged [discrepancy-theory]

The discrepancy-theory tag has no usage guidance.

**0**

votes

**0**answers

34 views

### Two sequence discrepancy and smallest boxes?

Take $p$ to be a prime and let $a_1,\dots,a_n\in\mathbb Z$ be some set of integers such that discrepancy of the set of fractional parts $$\{\frac{ma_1}p,\dots,\frac{ma_n}p\}$$ with $m\in\{1,\dots,p-1\}...

**3**

votes

**1**answer

325 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] ...

**1**

vote

**0**answers

40 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 ...

**1**

vote

**0**answers

40 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^...

**1**

vote

**0**answers

34 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 $...

**0**

votes

**0**answers

102 views

### Difference between Dirichlet Pigeonhole and Exponential sums bound in particular situation?

Dirichlet Pigeonhole says given prime $p$ and vector $(v_1,v_2,\dots,v_n)\in\mathbb Z^n$ there is an integer $m$ such that the vector $m(v_1,v_2,\dots,v_n)\bmod p$ lies in box $[-p^{(n-1)/n}-1,p^{(n-1)...

**1**

vote

**0**answers

40 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(...

**0**

votes

**0**answers

124 views

### An elementary size bound in number theory?

Given integer $a$ of size $R^\alpha$ with $\alpha\in(0,1)$ and $t$ large primes $R_i$ of roughly same size $R$ what is the smallest $T$ one needs so that there is an integer $0<K<R$ with as ...

**0**

votes

**0**answers

138 views

### Does something close to pigeonhole guarantee fullrank here at $\alpha\leq\frac1{16}$?

Fix a small ${\epsilon}>0$ and take a very large $n>0$.
We say integers $A,B,C,D,A',B',C',D'$ satisfy property $P[n]$ if $A,B$ is coprime, $C,D$ is coprime, $A',B'$ is coprime and $C',D'$ is ...

**0**

votes

**0**answers

147 views

### Could a full rank linear system arise from this construction?

Fix a small ${\epsilon}>0$ and take a very large $n>0$.
We say integers $A,B,C,D,A',B',C',D'$ satisfy property $P[n]$ if $A,B$ is coprime, $C,D$ is coprime, $A',B'$ is coprime and $C',D'$ is ...

**0**

votes

**0**answers

41 views

### On existence of certain vectors from moduli of structured vectors?

Fix a small ${\epsilon}>0$ and take a very large $n>0$.
Pick uniformly random integers $A,B,C,D,A',B',C',D'$ with $A,B$ is coprime, $C,D$ is coprime, $A',B'$ is coprime and $C',D'$ is coprime ...

**0**

votes

**0**answers

86 views

### Existence of certain diophantine equations

Given large enough integer $m$ and $3\leq t=O(1)$ integers $m<a_1,a_2,\dots,a_{t-1},a_t<2m$ is there $n\in\Bbb N$ such that there is coprime $n<u,v<c\cdot n$ at fixed $c>1$ with $$ux_i+...

**1**

vote

**0**answers

180 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))}.$$
...

**5**

votes

**1**answer

130 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,\...

**2**

votes

**2**answers

70 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 ...

**11**

votes

**2**answers

649 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 ...

**1**

vote

**1**answer

95 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$...

**2**

votes

**1**answer

145 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 \...

**3**

votes

**0**answers

283 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 $$...

**2**

votes

**2**answers

692 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/...

**3**

votes

**0**answers

74 views

### Are all $k$-regular graphs $k+1$-partite with sets of almost equal size?

Let $G$ be a $k$-regular graph on $n$ vertices. Is it true that we can find a partition the vertex set of $G$ into $k+1$ sets of roughly equal size (each of size at least $\lfloor \frac{n}{k+1} \...

**2**

votes

**1**answer

257 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 ...

**0**

votes

**0**answers

71 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 ...

**2**

votes

**0**answers

61 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 ...

**4**

votes

**0**answers

119 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 ...

**3**

votes

**1**answer

222 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 ...

**5**

votes

**1**answer

279 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$ ...

**2**

votes

**0**answers

121 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{...

**5**

votes

**1**answer

237 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 ...

**1**

vote

**1**answer

54 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 ...

**1**

vote

**1**answer

91 views

### Beck-Fiala for other discrepancies

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

**7**

votes

**1**answer

323 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, ...

**9**

votes

**1**answer

546 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 ${\...

**9**

votes

**3**answers

930 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 ...

**7**

votes

**1**answer

143 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?
...

**40**

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$ ...