co.combinatorics – Decomposing square of side length $n$ into $n$ squares in a certain “maximal” way

I was wondering if anything is known about this problem. We are given a square of side length $n$ and we wish to embed $n$ smaller (integer) squares inside it such that the sum of the side-lengths of the squares inside is maximised. Let $f(n)$ be the maximum sum of side-lengths one can produce in this way. I have computed some values of $f(n)$, and have displayed them below. Apologies for the handwritten drawing, but I think the picture does help explain what I’m trying to get at.

enter image description here

The inequalities I have highlighted in red are because I am unsure if this is the maximum that can be achieved. In particular, for $n=8$ we don’t even use $8$ squares, but I cannot figure out a configuration of $8$ squares that beats $20$. (I have reason to believe that $f(8)leq 21$, and it would be nice if this could be attained with equality.) The values I have written as equality I am more sure about, based on exhaustive computer simulation. Is anything known about this function $f$? Even basic upper and lower bounds would be really helpful. It certainly seems to be roughly $n^{3/2}$.

solution verification – $Msubset N$ for $R$-modules $M,N$ if $S_{mathfrak m}^{-1}Msubset S_{mathfrak m}^{-1}N$ for all maximal ideals $mathfrak msubset R$?

Consider the following proposition (with proof) taken from S. Lang’s “Algebraic Number Theory”:

Proposition $mathbf{18}$. Let $A$ be a Dedekind domain and $M,N$ two modules over $A$. If $mathfrak p$ is a prime of $A$, denote by $S_{mathfrak p}$ the multiplicative set $A-mathfrak p$. Assume that $S_{mathfrak p}^{-1}Msubset S_{mathfrak p}^{-1}N$ for all $mathfrak p$. Then $Msubset N$.

Proof. Let $ain M$. For each $mathfrak p$ we can find $x_{mathfrak p}in N$ and $s_{mathfrak p}in S_{mathfrak p}$ such that $a=x_{mathfrak p}/s_{mathfrak p}$. Let $mathfrak b$ be the ideal generated by the $s_{mathfrak p}$. Then $mathfrak b$ is the unit ideal, and we can write

$$1=sum y_{mathfrak p}s_{mathfrak p}$$

with elements $y_{mathfrak p}in A$ all but a finite number of which are $0$. This yields

$$a=sum y_{mathfrak p}s_{mathfrak p}a=sum y_{mathfrak p}x_{mathfrak p}$$

and shows that $a$ lies in $N$, as desired.

My first question is mainly concerned with the emphasised part and my second, more generally, with which of the assumptions of the proposition are necessary.

So, first regarding the emphasised part. From my understanding we consider the ideal

$$I=sum_{mathfrak p} Rs_{mathfrak p}$$

and claim that this ideal is the unit ideal. As far as I can tell this is a consequence of the following observation:

Maximal ideals are in particular prime and hence occur among the $mathfrak p$. Pick any maximal ideal $mathfrak m$ and note that $s_{mathfrak m}in I$ but $s_{mathfrak m}notinmathfrak m$ by definition. Hence $I$ is not contained in any maximal ideal and so has to be the unit ideal (as every proper ideal is contained in some maximal ideal).

Is this the correct way to think about it? I have found similar claims at some other places but never the full argument spelled out (which I have problems to grasp).

On to the second question: what is really needed for this to work? I think Dedekind domain can be drastically weakened to commutative (from what I understand this is not really needed but a subtle detail I do not deem too important for my question) unital ring. The Dedekind assumption is likely due to the book being on Algebraic Number Theory. However, I am also not sure about the assumption on all primes. The argument I gave above only uses the assumption on all maximal ideals (which makes no difference in a Dedekind domain but in general). I know that for a similar theorem equivalence in the cases of all primes and all maximal ideals holds (see here for instance).

So I claim the following from the aforegoing analysis:

Claim. Let $R$ be a commutative unital ring and $M,N$ two modules over $R$. If $mathfrak m$ is a maximal ideal of $R$, denote by $S_{mathfrak m}$ the multiplicative set $Rsetminusmathfrak m$. Assume that $S_{mathfrak m}^{-1}Msubset S_{mathfrak m}^{-1}N$ for all $mathfrak m$. Then $Msubset N$.

It might be possible to reduce this statement to the one I linked earlier (this one) but I am not sure if and how. Also, I could not find a more general reference for Prop. $18$ which makes me wonder. The books on Commutative Algebra and Abstract Algebra I checked did not seem to contain something similar either.

Thanks in advance!

nt.number theory – Finite groups arising as Galois groups of maximal unramified extension of number fields

I was wondering if it is known for which number fields the maximal unramified (non-abelian) extension is of finite degree or do we know the finite groups that arise as the Galois groups of these finite degree maximal unramified extensions.

I have seen the trivial group and the group of two elements as these Galois groups but not beyond that.

Thanks in advance.

Norm of maximal order in quaternion algebra

Let $B$ be a quaternion algebra over $mathbb{Q}$ that is a division algebra over $mathbb{R}$. The theorem of Hasse-Schilling tells us that the image of the reduced norm of $B^times$ is $mathbb{R}^+$.

Let $M$ be a maximal order in $B$. What is known regarding the image of the reduced norm of $M$? To be more specific: let $S$ be the set of primes for which $B$ ramifies. Can we find for every $p notin S$ an element of reduced norm $p^k$ for some arbitrary odd $k$?

order theory – Verification of a maximal antichain

In order theory, an antichain (Sperner family/clutter) is a subset of a partially-ordered set, with the property that no two elements are comparable with each other. A maximal antichain is the antichain which is not properly contained in another antichain. Let’s take the power set of ${1,2,ldots, n}$ as our partially-ordered set, here the order is given by inclusion. Then my question is, for any given antichain of this partially-orded set, is there any polynomial-time algorithm (with respect to $n$) to verify that this antichain is indeed “maximal”? In other words, verifying that any subset of ${1,2,ldots, n}$ is either contained in, or contains some set from the antichain. Here such algorithm should have polynomial run-time for ANY antichain.

pr.probability – Design a random variable which has the maximal correlation with another random variable

$Y$ is a Gaussian distributed random variable with zero mean and known variance: $Ysim N(0,sigma_y)$. We measure $Y$ with a sensor, which is corrupted by white Gaussian noise: $Z=Y+V$; $Vsim N(0,sigma_v)$.

How can I design a random variable $X$ depending on $Z$, $sigma_y$, $sigma_v$, and $sigma_x$ which results in $X$ having the distribution $Xsim N(0,sigma_x)$ and having a maximal correlation with $Y$?

Initial idea: We can take $hat{Y}$, the minimum mean square estimation (MMSE) of $Y$, and let $X=that{Y}$ with $t$ chosen to ensure that $X$ has the desired variance. But later I found this intuitive idea is not correct. I wonder if someone can answer this question.

oa.operator algebras – When the adjoint of an unbounded operator on a Hilbert space coincides with the formal adjoint on its maximal domain?

This is a copy of

Suppose we have a closable and densely defined operator $A$ with a domain $dom(A)$ which is a subspace of a Hilbert space $mathcal{H}$.
Let $mathcal{H}$ have an orthonormal basis ${e_n}_{n=1}^infty$.
So the operator $A$ can be viewed as an infinite matrix $A_{ij}$.

We know that there is a usual procedure to define $A^*$ with its domain $dom(A^*)$.
Now consider the formal adjoint operator $A_* = {overline{A_{ji}}}$ with the domain $dom(A_*)$.
Are there some simple conditions on $A$ when these domains coincide: $dom(A^*) = dom(A_*)$?

What can be said on this matter if $A_{ij}$ is a finite-band matrix?
Or when $A$ is formally self-adjoint ($A_{ij} = overline{A_{ji}})$?

complexity theory – Find maximal clique consisting of at least half of the vertices

Assume that we are given an undirected graph $G$ of n vertices. For this graph, we also know that there is a clique of size $c$, for some $cgeq lfloor n/2 + 1rfloor$. In other words, the majority of the vertices will belong to this clique. This clique may or may not be maximal; however, given these assumptions it will definitely be a subgraph of the maximum clique of $G$.

My goal is to find the most efficient algorithm to find the maximum clique of the graph. If the maximum clique is not unique, finding one of them is fine.

In general, $G$ won’t be planar or perfect graph and to the best of my knowledge there is no exponential or linear-time algorithm to solve this problem.

I thought that, one way is to do an exhaustive search of all $nchoose c$ induced subgraphs until I find a clique $C$. Then, one can keep adding vertices to $C$ such that they connect to all vertices currently in $C$ until this clique cannot be enlarged anymore. Then, $C$ will be one maximum clique.
Assuming that $n$ is not too large, maybe $n < 50$, do you think that this is a reasonable method given that $nchoose c$ is large? Is there a more efficient algorithm?

One small optimization is to exclude all vertices with degree $< c-1$ from consideration.