14
votes

### Current state of the Komlos conjecture on vector balancing

As far as I know, the state of the art is that one can actually achieve $K=K(n)=O(\log^{\frac{1}{2}} n)$ independent of the dimension $d$. Moreover, one can actually find the weights $w_i$ via an ...

10
votes

Accepted

### Current state of the Komlos conjecture on vector balancing

For fixed $d$, one can actually achieve a bound independent of $n$. More precisely, $K=K(d)=O(\sqrt{d})$ is fine, uniformly in $n$.
Proof : the unit ball of $\mathbb{R}^d$ can be covered by $2C^d$ ...

6
votes

### Can we balance $2$-powers?

UPDATED. I've changed the verification strategy and computationally proved the statement for all $k\leq 30$, using the following randomized algorithm.
Randomized algorithm. For a given list of $k$ ...

4
votes

### Estimates on the discrepancy of random sequences

$\mathbb{E}[D(N; X)]$ is of order $N^{-1/2}$. This, and more precise information, follows from the analysis of the Kolmogorov-Smirnov test [1].
See, in particular, [2] and the references described on ...

4
votes

Accepted

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

I actually think there is a more significant flaw. A counterexample to the centered inequality is $\rho = \frac{1}{2}$ and $A = \{1,2,\dots,\frac{N}{2}\}$. Indeed, we always have $\sum_{n \in A, n \...

3
votes

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

As I understand it, you might be interested in a quantity called the inverse of the star-discrepancy. Given dimension $d$ and some $\varepsilon > 0$, the inverse of the star-discrepancy $n(d,\...

3
votes

Accepted

### the sum of fractional parts times the ordinary powers

As Gerry already commented, your formulas are equivalent to a reciprocity theorem of Tom Apostol; see, e.g., the bibliography in this paper (Apostol's paper is too old to be on the arXiv): Your sums ...

2
votes

Accepted

### Distribution-free statistics on compact Lie groups

From the perspective of statisticians, I will suggest two chapters in
Parthasarathy, Kalyanapuram Rangachari. Probability measures on metric
spaces. Vol. 352. American Mathematical Soc., 1967.
...

2
votes

### Bounded version of linear and quadratic Hasse--Minkowski theorem

The linear case is Siegel's lemma. I do not know the quadratic case: Cassels does not have it, perhaps O'Meara does. Note that the regulator is closely related where we seek a representation of $1$ by ...

2
votes

Accepted

### Reference request - parallel rectangles discrepancy theory

Perhaps the issue is to establish a tight lowerbound for the discrepancy of $n$ points in dimension $d$ with respect to $d$-dimensional boxes.
In
Matousek, Jiri, ed. Geometric discrepancy: An ...

1
vote

### Can we balance $2$-powers?

Fedor Petrov's comment shows than for each $k$ there are only finitely many cases for $x_1$ to check, so I wrote a program to do this. The positive answer is already obtained for all natural $k\le 10$....

1
vote

Accepted

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

I wound up contacting Dr. János Pach (an expert in relevant fields) regarding the problem on the recommendation of my first professor. Apparently the problem (originally in a slightly different form) ...

1
vote

### Is the bound of Spencer on discrepancy tight?

Yes, the bound is tight, and here is a proof sketch. In fact, we will show that a random sequence of subsets $\mathcal{S} = \{S_1, S_2, \dots, S_m\}$ provides the lower bound up to constants. ...

1
vote

### Discrepancy of the Halton set

It is true that in general there is a difference between "sets" and "sequences". The later, unlike sets, may have repeating elements, and also unlike sets, the order of elements ...

1
vote

### Bounded version of linear and quadratic Hasse--Minkowski theorem

For the first question, the answer is yes; you can find the statement and a proof in Cassels (pp 86-89). A far reaching generalization was obtained by J. Vaaler in 1987 concerning the height of a ...

1
vote

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

This may not be what the OP seeks, but the paper below contains quite a bit
of detailed numberical tables for low
star-discrepancy sets.
Star discrepancy $d^*$ takes the supremum over rectangles that ...

1
vote

### Quantified imbalance in signed graphs

Ad 1: I take this to ask for whether 'horribly imbalanced' graphs even exist, and, more generally, what can be said about the necessary conditions you imposed on them. This is what this answer/comment ...

1
vote

### Occurrence of simultaneous small remainders?

This is not always true. Suppose that $c_1+c_2=c_0$. Then $pc_1+pc_2\equiv pc_0\pmod{n}$. Hence if $pc_1\bmod n$, $pc_2\bmod n$ are in $[0, n^r]$, then $pc_0\bmod n$ is in $[0, 2n^r]$, which falls ...

1
vote

### An extremal combinatorics problem involving column summation

If you relax the power-of-two condition, you can contrive examples for the $\beta = 1/2$ and $\alpha = 1$ case that require all columns to be used. Choose a large prime $p$. Let $A$ be the $p \times ...

Only top scored, non community-wiki answers of a minimum length are eligible

#### Related Tags

discrepancy-theory × 48co.combinatorics × 23

nt.number-theory × 14

analytic-number-theory × 10

reference-request × 6

diophantine-approximation × 5

hypergraph × 5

pr.probability × 4

graph-theory × 3

discrete-geometry × 3

exponential-sums × 3

probabilistic-number-theory × 3

linear-algebra × 2

ca.classical-analysis-and-odes × 2

matrices × 2

st.statistics × 2

lattices × 2

coding-theory × 2

extremal-combinatorics × 2

arithmetic-progression × 2

diophantine-geometry × 2

ag.algebraic-geometry × 1

fa.functional-analysis × 1

gr.group-theory × 1

real-analysis × 1