# Tagged Questions

**5**

votes

**0**answers

47 views

### Why have most maximal cliques of Paley graphs odd size?

I ask this question mainly by curiosity.
See here for definitions and a plot of the clique numbers of the Paley graphs for the primes $p\equiv 1 \pmod 4$ up to $10000$.
Is there an ...

**6**

votes

**0**answers

148 views

### Non-trivial bounds for polynomials at a fixed point

Let $f$ be a polynomial of degree $d$. Of course $|f(z)|\sim C|z|^d$ as $|z|\rightarrow\infty$ but also, since any polynomial is completely determined by its values at any $d+1$ points, we may ask how ...

**5**

votes

**1**answer

290 views

### Are there number-theoretic graphs that are far from being isomorphic

I say that two graphs $G_1=(V_1,E_1)$, $G_2 = (V_2,E_2)$
with the same number of vertices, edges,
are $\epsilon$-far from being isomorphic, if for any bijection between $V_1$ and $V_2$, the fraction ...

**-3**

votes

**1**answer

116 views

### How many sequences of length n satisfy these constraints? [closed]

I want to count the number of unique sequences of length n with the following constraints.
Each element of the sequence is an integer in $\lbrace 1,2,\dots,n\rbrace$.
Each two adjacent elements of ...

**12**

votes

**2**answers

460 views

### The sum of the carries when adding and multiplying two numbers in base p

Let $\sigma_p(m,n)$ (resp. $\pi_p(m,n)$) denote the sum of the carries when adding
(resp. multiplying) the numbers $m=\sum_{k\ge0}m_kp^k$ and $n=\sum_{k\ge0}n_kp^k$ using base-$p$ arithmetic where ...

**3**

votes

**1**answer

221 views

### Dynamics in the integers - Floor function

Let $\alpha$ be an irrational with $0<\alpha<1$. Consider the function given by \begin{align*}
f: &\mathbb{N}\longrightarrow \mathbb{N}\\ &x\longmapsto [ \alpha\cdot x]\end{align*} where ...

**12**

votes

**1**answer

668 views

### Szemeredi's theorem in the Gaussian integers

Suppose that $S\subseteq\mathbb{Z}[i]$ has the following properties:
For convenience, let $A_n = \{z : z\in\mathbb{Z}[i], \text{Nm}(z)\le n\}$
$$\limsup_{n\rightarrow\infty} \frac{|S\cap ...

**35**

votes

**1**answer

874 views

### Do runs of every length occur in this sequence?

This is a repost from user r.e.s's unsolved Math Stack Exchange question: Do runs of every length occur in this string? That question was derived from my original question on the subject: Does this ...

**6**

votes

**1**answer

243 views

### A parity counting problem for subsets over finite fields

Let ${\mathbb F}_p$ be the prime field of $p$ elements and $b$ be an element in ${\mathbb F}_p$.
For a subset $T\subseteq {\mathbb F}_p$, define
$$Bias(T)=|N_e( {\mathbb F}_p,b)-N_o( {\mathbb ...

**13**

votes

**1**answer

472 views

### When is $(q^k-1)/(q-1)$ a perfect square?

Let $q$ be a prime power and $k>1$ a positive integer. For what values of $k$ and $q$ is the number $(q^k-1)/(q-1)$ a perfect square, that is the square of another integer? Is the number of such ...

**0**

votes

**0**answers

118 views

### a question on sum of Gaussian binomial coefficients

I was trying to calculate something and at some point I get the following sum:
\begin{equation}
\sum_{t=0,t \text{ even}}^{s}{s+3n \brack s-t}\sum_{i = 0}^{t/2}q^{2i^2}{t/2+2n-i \brack t/2-i}{n ...

**11**

votes

**0**answers

346 views

### Erdos multiplication problem revisited

The well-known problem is acquiring a cardinality of the set of distinct numbers in the multiplication table n x m.
The very problem has been discussed in-depth and, as such, I require no further ...

**3**

votes

**3**answers

302 views

### How to find an integer set, s.t. the sums of at most 3 elements are all distinct?

How to find a set $A \subset \mathbb{N}$ such that any sum of at most three Elements $a_i \in A$ is different if at least one element in the sum is different.
Example with $|A|=3$: Out of the set $A ...

**15**

votes

**0**answers

322 views

### Spencer's “six standard deviations” theorem - better constants?

This question is about Joel Spencer's famous "six standard deviations" theorem. The theorem says that when
$$
L_i(x_1,\dots,x_n) = a_{i1} x_1 + \dots + a_{in} x_n, \quad 1 \leq i \leq n,
$$
are $n$ ...

**11**

votes

**2**answers

372 views

### how to find cubic polynomial that an unknown subset of a set of integers satisfies

I have a set, $S$, of positive integers and I have reason to believe that some infinite subset of them may be parametrized by a cubic polynomial with integer coefficients evaluated at integer ...

**18**

votes

**3**answers

615 views

### Number of primitive $n$th roots with positive versus negative real parts

Does anyone know a reference to the following results, which I can prove, but I suspect may be known. Let $R(n)$ denote the number of primitive $n$th roots of unity with positive real part, and $L(n)$ ...

**8**

votes

**2**answers

331 views

### Sum and product estimate over integers, rationals, and reals

My question is the following: is finding a lower bound for $|A+A\cdot A|$ (as a function of $|A|$) where $A$ is any finite subset of the positive integers equivalent to finding the same lower bound ...

**11**

votes

**1**answer

577 views

### Colourings of $\mathbb Q\times \mathbb Q$ in three colours

Using two-adic valuation Monsky coloured $\mathbb Q\times \mathbb Q$ in red, blue, and green, so that on each line points of at most two colours are present.
Question. I would like to know if there ...

**4**

votes

**1**answer

213 views

### Circulant matrix with integer entries and determinant 1 or -1

CONJECTURE
Let $A= (c_0,c_1,\ldots,c_n)$ be a circulant matrix, i.e if $(c_0,c_1,\ldots,c_n)$ is the first column of $A$ then the $i$th column of $A$ is obtained by applying the permutation ...

**4**

votes

**3**answers

577 views

### Analogy between Integers and Permutations

I am reading Andrew Granville's Anatomy of Integers and Permutations where it is argued the factorization of a permutation into disjoint cycles is analogous to the factorization of a number into prime ...

**0**

votes

**0**answers

116 views

### Non existence (or existence) of a set that is equidistributed modulo $q$ for every $q$

I have been thinking about some set that is equidistributed modulo $q$,
uniformly in $q$ in some sense. I was starting to think this particular condition, which I describe below, is too strong and ...

**6**

votes

**5**answers

580 views

### What makes a set random?

There are many results in number theory, where the existence
of some $B \subseteq \mathbb{N}$ with certain properties is proved by
a probabilistic argument employing "random sets". One such example
...

**7**

votes

**0**answers

103 views

### Ordering subsets of the cyclic group to give distinct partial sums

Suppose that you are given a set $S$ of $k$ nonzero elements from $\mathbb{Z}_n$. Is it always possible to order the elements of $S$, say $a_1,a_2,\dots,a_k$ in such a way that the partial sums ...

**2**

votes

**1**answer

252 views

### Bound for a combinatorial sum

I was playing around with a problem and I obtained a certain
combinatorial sum. I was wondering if there was a way to simplify or bound it.
I have a real valued function $f$, which satisfies $|f(x)| ...

**4**

votes

**2**answers

344 views

### Can we sometimes define the parity of a set?

Suppose that ${n\choose k}, {n-1\choose k-1}, \ldots, {n-k+1\choose 1}$ are all even. (This happens for example if $k=2^\alpha-1$ and $n=2k$.) In this case, can we select ${n\choose k}/2$ sets of size ...

**4**

votes

**1**answer

281 views

### Existence of a certain subset of natural numbers equidistributed modulo $m$ for every $m$

I was talking to a friend and the following set $S$ came up.
Let $f$ be some real valued function tending to infinity.
Let $S$ be a subset of natural numbers such that $|S \cap [1,N]| = N^{\delta}+ ...

**1**

vote

**1**answer

240 views

### An infinite product: combinatorial interpretation

It is an undergraduate exercise to show that the generating function for the sequence of unrestricted integer partitions $p(n)$ is the celebrated infinite product
...

**3**

votes

**0**answers

97 views

### Number cubes with consecutive line sums

This is barely of research interest, but I'd classify it as a curiosity with connections to combinatorics.
The problem is to place integers in an $n \times n \times n$ array so that all $3n^2$ line ...

**35**

votes

**6**answers

2k views

### Placing numbers $1,2,\ldots,n^3$ in a cube so that numbers of any two adjacent unit subcube are coprime

This is a question first I asked in SE but since there was no suggestion or solution, I decide to put it here.
Consider an $n\times n \times n$ Cube containing $n^3$ unit cubes. Is it possible to ...

**2**

votes

**2**answers

835 views

### Number of 1 in binary representation of n

Let $1(n)$ be the number of digits $1$ in binary representation of number $n$.
For example, $13=1101_2$ so $1(13)=3\\$
Is there explicit form of $\,\,\sum{1(i)x^i} $?
I checked OEIS and didn't find ...

**9**

votes

**3**answers

747 views

### Could a perfect squared square be split into two perfect squared squares?

This is a geometric puzzle though it might conceivably
also define a special class of Pythagorean triples.
A perfect squared square PSS is a square (as a plane figure)
partitioned into smaller ...

**4**

votes

**1**answer

372 views

### Balog-Szemeredi-Gowers with dilates of sets

All sets are assumed to be finite subsets of the integers.
The additive energy of two sets $E(A,B)$ is defined as the number of solutions to $a+b=a'+b'$ with $a,a'\in A$ and $b,b'\in B$. The ...

**1**

vote

**1**answer

196 views

### Simplifying a sum in terms of divisor function Cauchy products

I'm trying to simplify this combinatorial looking sum:
$$\sum_{ax+by=n}_{(a,x,b,y)\in \mathbb{N^4}}\max{\{a,b\}}$$
In terms of possibly some scaled divisor functions plus a Cauchy product/convolution ...

**3**

votes

**0**answers

138 views

### What is the function like when its Mobius inversion is $\sum_{w|r, (w,t)=1}\mu(w)q^{r/w}$?

Everyone, I am now reading a paper named The Irreducible Factors of $(cx+d)x^{q^m}-(ax+b)$ over $GF(q)$, http://qjmath.oxfordjournals.org/content/14/1/61.extract. And Iâ€™m confused with one of its ...

**5**

votes

**1**answer

273 views

### Number of partitions whose blocks form arithmetic progressions

As is known, the set $\{1,\ldots,n\}$ has $2^n$ many subsets and $B_n$ (the $n$th Bell number) many partitions, where clearly $B_n<2^{2^n}$ and it is actually known that $B_n<n^n$ for large $n$. ...

**1**

vote

**0**answers

52 views

### A lower bound on the number of matrices whose image contains all multiples of $p^e$

Let $0\leq e<e^\prime$ be integers. Now suppose $N$ is the number of $n\times n$ matrices over the ring $R:=\mathbb{Z}/p^{e^\prime}\mathbb{Z}$ (where $p$ is prime) such that ...

**8**

votes

**0**answers

123 views

### Erdös-Fuchs Theorem for multivariate linear forms

Let $A$ be an infinite set of positive integers, and denote by $r(n)$ the number of solutions to the equation $a+a'=n$, with $a,\, a' \in A$.
It is not very difficult to show that if $r(n) > 0$ ...

**7**

votes

**2**answers

871 views

### Linear independence of the square roots over Q

Does there exist a real number $a$ such that the numbers $\sqrt{n^2 + a^2}$ (for all natural $n$) are linearly independent over the field of rational numbers? It is evident that $a$ cannot be ...

**0**

votes

**0**answers

40 views

### Minimize $td-2\sum_{i=0}^{t-1} w_k(i)$ where $w_k(i)$ is the sum of the base-$k$ digits of $i$

Let $K_k^n$ denote the $n$-fold cartesian product of the complete graph on $k$ vertices, and let $[R,T]$ be the edge cut, consisting of the edges between complementary vertex sets $R$ and $T$.
I ...

**4**

votes

**2**answers

401 views

### summation of products of combinatorials

For any natural number $N$ and $0\le n\le N$ define
$$
f(n) = f(n,N) = \frac{1}{(N+1)!} \sum_{\substack{{S\subset \{1,\ldots,N\}} \\ {|S|=n}}} \prod_{s\in S} s.
$$
(The empty product is interpreted ...

**1**

vote

**1**answer

264 views

### Known results on cyclic difference sets

Is there any infinite family of $v$ for which all the $(v,k,\lambda)$-cyclic difference sets with $k-\lambda$ a prime power coprime to $v$ have been determined?
A subset $D=\{a_1,\ldots,a_k\}$ of ...

**3**

votes

**1**answer

536 views

### Estimate the sum $\sum_{k=1}^n \frac{2^k}{k}$ [closed]

I am concerned with the following sum
$$\sum_{k=1}^n \frac{2^k}{k}_{\displaystyle ~.}$$
It seems that sum must be computed by someone, but I do not know.
By the way, I can figure out a power ...

**3**

votes

**0**answers

60 views

### Distribution of the evaluation (at a non-trivial root of -1) of polynomials with small coefficients

When we studied some cryptographic protocol, we came accross the following problem, which seems linked to the uniformity of the residues of small multiplicative subgroups of $\mathbb{F}_q$.
Problem
...

**7**

votes

**2**answers

280 views

### Sets whose elements are mutually “weakly” coprime?

Fix $n$ and $k$. I want a set $S\subseteq\{1,\ldots,n\}$ with the property that for every $x\in S$,
$$\mathrm{gcd}\bigg(x,\prod_{y\in S\setminus\{x\}}y\bigg)<\frac{x}{k}.$$
How small should a ...

**3**

votes

**1**answer

270 views

### A partition problem

This question is motivated by an old math contest problem, and is a generalization of the original problem. I will write out the original problem as motivation.
Let us say that $n$ is $p$-Savage, for ...

**1**

vote

**0**answers

75 views

### Quadratic transformation of hypergeometric function 2F1

I want to know whether there is some transformation between
$_2F_1(a,b;c;x)$ and $_2F_1(a',b';c';x(1-x))$.
Here is an example called the Kummer quadratic transformation, which may be known to most of ...

**21**

votes

**3**answers

2k views

### How many different numbers can be obtained as product of first $n$ natural numbers?

Let m and n be natural numbers, and consider the set of all possible products of m (not necessarily distinct) elements from the set $\{1,2,\ldots,n\}$, that is consider the set
$\{1^{a_1} \cdot ...

**4**

votes

**1**answer

447 views

### a conjecture in sum-free sets

Let $ A $ be a set of non-zero integers. Then $A$ contains a sum-free subset $B$ of size $ |B|> \frac{|A|}{3} $ (a result of ErdÅ‘s). It is conjectured that RHS can be improved to $\frac{|A|}{3} ...

**0**

votes

**0**answers

101 views

### Multivariate generating function

I am investigating the perturbation of the Jordan canonical form. In my work I must calculate the number of ways to factor $p^ {n-k} q^k$ where $p$ and $q$ are distinct primes ...

**19**

votes

**1**answer

505 views

### Avoiding multiples of $p$

Let $p$ be a prime number and $P=\{1,2,...,p-1\}$
In how many ways we can sum all the elements of $P$ in such a way that we will reach a multiple of $p$
only when we sum the last summand?
For ...