\lecture[1]{ غیر یکتا در دامنه‌های صحیح}{lecture-text}

\subtitle{درجهٔ \lr{tame} و \lr{catenery}}

\date{۱۶ دی ۱۳۸۷}
\newcommand\NN{\mathbb N}

\begin{document}

\begin{frame}
  \maketitle
\end{frame}

\begin{frame}\frametitle<presentation>{چشم‌انداز}
  \tableofcontents
\end{frame}


\section{پیشگفتار}
\subsection{چکیده}
\begin{frame}{چکیده}
مطالعهٔ ویژگی‌های ترکیبیاتی خاصی از تجزیه‌های غیریکتا موضوع اصلی دسته‌ای از تحقیقات کنونی است. دانسته‌های حال حاضر در مورد دو ناوردای ترکیبیاتی، درجهٔ \lr{catenary} و \lr{tame}، حتی در حالت مونوئیدهای عددی بسیار کم است. در این گزارش تحقیقاتی کارهای انجام شدهٔ بر روی این دو ناوردا برای مونوئیدهای عددی تولید شده توسط مجموعه‌های تصاعدی تعمیم‌یافته را مورد بررسی قرار می‌دهیم. در این راستا به محاسبهٔ این دو ناوردا در این حالت می‌پردازیم و با بررسی مقادیر بدست آمده خواهیم دید که تفاضل این دو ناوردا می‌تواند به اندازهٔ دلخواه بزرگ باشد حتی اگر کاردینال مجموعهٔ مولد مینیمال پایا باقی بماند.
\end{frame}
\subsection{مقدمه}
\begin{frame}{مقدمه}
چندین ناوردای عددی وجود دارد که رفتار تجزیه‌های غیریکتا را در یک دامنهٔ صحیح مشخص می‌کنند. کارهای اولیهٔ انجام شده در این راستا بر مطالعهٔ طول تجزیه‌های مختلف برحسب عناصر تحویل‌ناپذیر متمرکز بود. مجموعه‌های دلتا و انعطاف (\lr{elasticity}) دو نمونه از این ناورداها بودند که نشان می‌دادند یک دامنهٔ صحیح چقدر از دامنهٔ تجزیهٔ یکتا یا نیمه‌یکتا (یعنی دامنه‌هایی که طول تجزیه‌های مختلف هر عنصر به عناصر تحویل‌ناپذیر یکسان باشند) دور هستند. در سال‌های اخیر ناورداهای دیگری در مقالات پدیدار شده‌اند. درجهٔ \lr{catenary} و درجهٔ \lr{tame} دو نمونه از این ناورداها هستند. 
\end{frame}
\section{مقدمات}
\subsection{مونوئیدهای عددی}
\begin{frame}{مونوئیدهای عددی}
منظور از یک مونوئید عددی $S$ عبارت است از یک زیرمونوئید از $(\NN_0,+)$، که $0\in S$ و $\NN\setminus S$ متناهی باشد. 
  \begin{itemize}
  \item هر مونوئید عددی دارای یک مجموعهٔ مولد مینیمال یکتا است. 
  \item $\max(\NN_0\setminus S)$ را عدد فرابنیوس $S$ می‌نامند و با $g(S)$ نمایش می‌دهیم.
  \item 
اگر 
$0<n_0<\ldots<n_p$ 
اعداد صحیح مثبت باشند و 
$\gcd\{n_i\}=1$
آنگاه مونوئید عددی تولید شده توسط این اعداد را به صورت زیر تعریف می‌کنیم:
$$\langle n_0,\ldots,n_p\rangle=\NN_0 n_0+\ldots+\NN_0 n_p=\left\{\sum z_i n_i\big |z_i\in\NN_0\right\}$$
  \item 
بر روی $S$ یک ترتیب جزئی $\leq_S$ به این صورت تعریف می‌شود که $a\leq_S b$ اگر و تنها اگر $b-a\in S$.
  \end{itemize}
\end{frame}

\begin{frame}
\begin{itemize}
\item 
تابع تجزیه $\varphi:\NN_0^{p+1}\rightarrow S$ را به صورت زیر تعریف می‌کنیم:
$$\varphi(z_0,\ldots,z_p)=z_0n_0+\ldots+z_pn_p.$$
\item
مجموعهٔ تجزیه‌های $n\in S$ را به صورت زیر تعریف می‌کنیم:
$$\factorization(n)=\varphi^{-1}(n)=\{(z_0,\ldots,z_p)\in\NN^{p+1}|z_0n_0+\ldots+z_pn_p=n\}.$$
\item
طول یک تجزیهٔ $z=(z_0,\ldots,z_p)\in\factorization(n)$ به صورت زیر تعریف می‌شود:
$$|z|=z_0+\ldots+z_p.$$
\item
مجموعهٔ طول‌های $n\in S$ را به صورت زیر تعریف می‌کنیم:
\[\len(n)=\{|z|\,\big|\, z\in\factorization(n)\}\subset\NN_0.\]
\item 
اگر 
$z=(z_۰,\ldots,z_p),z'=(z'_۰,\ldots,z'_p)\in\NN^{p+1}$ 
تعریف می‌کنیم:
$$\gcd(z,z')=(\min\{z_1,z'_1\},\ldots,\min\{z_p,z'_p\}),\frac{z}{z'}=z-z'$$
\end{itemize}
\end{frame}
\begin{frame}
\begin{itemize}

\item 
اگر 
$z=(z_۰,\ldots,z_p),z'=(z'_۰,\ldots,z'_p)\in\NN_0^{p+1}$ 
تعریف می‌کنیم:
$$\gcd(z,z')=(\min\{z_1,z'_1\},\ldots,\min\{z_p,z'_p\}),\frac{z}{z'}=z-z'$$
و فاصلهٔ بین $z$ و $z'$ را به صورت زیر تعریف می‌کنیم:
$$\dd(z,z')=\max\Big\{\Big|\frac{z}{\gcd(z,z')}\Big|,\Big|\frac{z'}{\gcd(z,z')}\Big|\Big\}$$
\item
فاصلهٔ دو زیرمجموعهٔ $X$ و $Y$ از $\NN_0^{p+1}$ را به شکل زیر تعریف می‌کنیم:
$$\dd(X,Y)=\min\{\dd(x,y)| x\in X, y\in Y\}$$
\end{itemize}
\end{frame}
\subsection{درجهٔ \lr{catenary}}
\begin{frame}{درجهٔ \lr{catenary}}
\begin{itemize}
\item
فرض کنید $n\in S$ و $z,z'\in\factorization(n)$. منظور از یک $N$-زنجیر تجزیه‌ها از $z$ تا $z'$ عبارت است از دنبالهٔ $z_0,\ldots,z_k\in\factorization(n)$ به طوری که 
$z=z_0$، $z'=z_k$ 
و 
$\dd(z_i,z_{i+1})\leq N$ 
بر ای هر  $i$.
\item
درجهٔ \lr{catenary} عنصر $n\in S$، $\cat(n)$ را کوچکترین عدد صحیح نامنفی $N$ تعریف می‌کنیم که هر دو تجزیهٔ $z$ و $z'$ از $n$ را بتوان با یک $N$-زنجیر تجزیه‌ها به هم وصل کرد.
\item 
درجهٔ \lr{catenary} مونوئید $S$ را به صورت زیر تعریف می‌کنیم:
\[\cat(S)=\sup\{\cat(n)|n\in S\}.\]
\end{itemize}
\end{frame}
\subsection{درجهٔ \lr{tame}}
\begin{frame}{درجهٔ \lr{tame}}
\begin{itemize}
\item
فرض کنید $n\in S$. برای $i\in\{0,\ldots,p\}$ تعریف می‌کنیم:
$$\factorization^i(n)=\{(z_1,\ldots,z_p)\in \factorization(n)| z_i\neq 0\}$$

\item
فرض کنید $n-n_i\in S$؛ تعریف می‌کنیم
\[\tame_i(n)=\max\{\dd(z,\factorization^i(n))|z\in \factorization(n)\}\]
و
\[\tame(n)=\max\{\tame_i(n)|n-n_i\in S, 1\leq i\leq p\}\]
و آنرا درجهٔ \lr{tame} عنصر $n$ می‌نامیم.
\item
درجهٔ \lr{tame} مونوئید $S$ را به صورت زیر تعریف می‌کنیم:
\[\tame(S)=\max\{\tame(n)|n\in S\}\]
\end{itemize}
\end{frame}

\section{مونوئیدهای حسابی تعمیم‌یافته}
\subsection{معرفی مونوئیدها}
%{مجموعه‌های تصاعدی تعمیم‌یافته}
\begin{frame}{معرفی مونوئیدهای تولید شده توسط دنباله‌های تصاعدی تعمیم‌یافته}

\begin{itemize}
\item
دنبالهٔ 
$a,ha+d,\ldots,ha+xd$
را که در آن $a$، $h$، $x$، و $d$ اعداد صحیح مثبت  باشند و $\gcd(a,d)=1$ یک دنبالهٔ تصاعدی تعمیم‌یافته می‌نامیم. 
\item 
اگر $n=qa+id$ و $0\leq i<a$، آنگاه $n\in S$ اگر و تنها اگر
$$\lceil\frac{i}{x}\rceil h\leq q$$
\item
اگر $n=qa+id$ و $0\leq i<a$، آنگاه
$$\max\len(n)=q-\lceil\frac{i}{x}\rceil(h-1)$$

\end{itemize}
\end{frame}
\subsection{درجهٔ \lr{catenary} و \lr{tame}}
\begin{frame}{درجهٔ \lr{catenary} و \lr{tame}}
\begin{itemize}
\item
فرض کنید 
$S=\langle a,ha+d,\ldots,ha+xd\rangle$ که  $a,d,h$، و  $x$
اعداد صحیح مثبت هستند، 
$\gcd(a,d)=1$،
 و  
$1\leq x\leq a-1$. آنگاه
\begin{itemize}
\item
\[\cat(S)=\lceil\frac{a}{x}\rceil h+d\]
\item 
\[\tame(S)=\omega(S)=\big(\lceil\frac{a-1}{x}\rceil +1\big)h+d\]
\end{itemize}
\end{itemize}
\end{frame}
\subsection{نتایج }
\begin{frame}{نتایج}
\begin{itemize}
\item 
عدد فرابنیوس مونوئیدهای عددی تولید شده توسط دنباله‌های تصاعدی تعمیم یافته به صورت زیر پیدا شده است:
\[g(S)=\lceil\frac{a-1}{x}\rceil ha+ad-a-d\]
فرض کنید
\[B=\frac{g(S)+n_p}{n_1}+1=(\lceil\frac{a-1}{x}\rceil +1)h+\frac{x-1}{a}d.\]
آنگاه
\[B-\tame(S)=\frac{x-1}{a}d\]
و
\[B-\cat(S)=\big(\lceil\frac{a-1}{x}\rceil+1-\lceil\frac{a}{x}\rceil\big)h+
\frac{x-1}{a}d\]
\end{itemize}
\end{frame}
\begin{frame}{نتایج}
\begin{itemize}
\item 
فرض کنید  
$(a\mod x)=1$. 
آنگاه 
$\cat(S)=\tame(S)$ 
در حالی که
$B-\cat(S)=(x-1)d/a$ می‌تواند به اندازهٔ کافی بزرگ باشد وقتی که $d$ به بینهایت میل می‌کند.

\item 
فرض کنید 
$(a\mod x)\neq 1$ 
و  $d$ را طوری انتخاب کنید که 
$(x-1)d<a$. 
آنگاه 
$\lfloor B\rfloor=\tame(S)$ در حالی که 
$B-\cat(S)=h+(x-1)d/a$ 
می‌تواند به اندازهٔ کافی بزرگ باشد وقتی که $h$ به بینهایت میل کند.
\end{itemize}
\end{frame}
\end{document}